Skip to content

Base Encoding Order and Fixing Fixed Point Bug for IdSortable#8

Merged
CMCDragonkai merged 2 commits intomasterfrom
baseencodingorder
Oct 21, 2021
Merged

Base Encoding Order and Fixing Fixed Point Bug for IdSortable#8
CMCDragonkai merged 2 commits intomasterfrom
baseencodingorder

Conversation

@CMCDragonkai
Copy link
Member

@CMCDragonkai CMCDragonkai commented Oct 21, 2021 •
edited
Loading

Description

  • IdSortable was generating bad timestamps because of fixed point off by 1 error
  • Base encodings don't necessarily preserve lexicographic order

Issues Fixed

Tasks

  1. - Made toFixedPoint check if the fractional becomes 1 and adds it to the integer
  2. - Changed Math.round to Math.floor in assignment of fractionalFixed to avoid 4096 in 12 bits in toFixedPoint
  3. - Added tests for checking edge conditions of close to 1 and close 0 for toFixedPoint and fromFixedPoint
  4. - Added tests to check if IdSortable is producing bad ids after a long time
  5. - Added tests to check if base encodings are preserving the same order, and demonstrating that base64 is not lexicographically ordered

Final checklist

  • Domain specific tests
  • Full tests
  • Updated inline-comment documentation
  • Lint fixed
  • Squash and rebased
  • Sanity check the final build

@CMCDragonkai CMCDragonkai self-assigned this Oct 21, 2021
@CMCDragonkai
Copy link
Member Author

CMCDragonkai commented Oct 21, 2021 •
edited
Loading

These changes were essential to fixing the IdSortable:

  // if the fractional is rounded to 1
  // then it should be added to the integer
  if (fractional === 1) {
    integer += fractional;
    fractional = 0;
  }
  // floor is used to round down to a number that can be represented by the bit size
  // if ceil or round was used, it's possible to return a number that would overflow the bit size
  // for example if 12 bits is used, then 4096 would overflow to all zeros
  // the maximum for 12 bit is 4095
  const fractionalFixed = Math.floor(fractional * (2 ** size));
  return [integer, fractionalFixed];

@CMCDragonkai
Fixed IdSortable's fixed point overflowing millisecond bits and demon…
4f7f908 
…strated base64 does not preserve lexicographic-order
@CMCDragonkai CMCDragonkai merged commit 99210c9 into master Oct 21, 2021
@CMCDragonkai CMCDragonkai deleted the baseencodingorder branch October 21, 2021 09:26
This was referenced Oct 21, 2021
Open
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

@CMCDragonkai CMCDragonkai

Labels

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Not all base encodings maintain lexicographic-order

1 participant

@CMCDragonkai