ChainSafe / ssz

Typescript implementation of Simple Serialize (SSZ)
https://simpleserialize.com/
Other
44 stars 17 forks source link

findDiffDepthi does not support 32 bits or more #370

Closed twoeths closed 1 month ago

twoeths commented 2 months ago

Describe the bug

Runs the below unit tests

describe("findDiffDepthi", () => {
  const testCases: {index0: number, index1: number, result: number}[] = [
    {index0: 0, index1: 1, result: 0},
    // 2 sides of a 4-width tree
    {index0: 1, index1: 3, result: 1},
    // 2 sides of a 8-width tree
    {index0: 3, index1: 4, result: 2},
    // 16-width tree
    {index0: 0, index1: 0xffff, result: 15},
    // 24-width tree
    {index0: 0, index1: 0xffffff, result: 23},
    // 28-width tree
    {index0: 0, index1: 0xfffffff, result: 27},
    // 29-width tree
    {index0: 0, index1: 0xffffffff >>> 3, result: 28},
    // 30-width tree
    {index0: 0, index1: 0xffffffff >>> 2, result: 29},
    // 31-width tree
    {index0: 0, index1: 0xffffffff >>> 1, result: 30},
    // below is 32 bits width tree, index0 and index1 stay in 2 sides
    {index0: 0, index1: 0xffffffff, result: 31},
    {index0: 0, index1: (0xffffffff >>> 1) + 1, result: 31},
    {index0: 0xffffffff >>> 1, index1: (0xffffffff >>> 1) + 1, result: 31},
    // below tests are same to first tests but go from right to left
    // similar to index0=0 and index1=1
    {index0: 0xffffffff - 1, index1: 0xffffffff, result: 0},
    {index0: 0xffffffff - 3, index1: 0xffffffff - 1, result: 1},
    {index0: 0xffffffff - 4, index1: 0xffffffff - 3, result: 2},
  ];
  for (const {index0, index1, result} of testCases) {
    it.only(`expect diffi between ${index0} and ${index1} to be ${result}`, () => {
      expect(findDiffDepthi(index0, index1)).to.be.equal(result);
    });
  }
});

has error

3 failing

  1) findDiffDepthi
       expect diffi between 0 and 4294967295 to be 31:

      AssertionError: expected -Infinity to equal 31
      + expected - actual

      --Infinity
      +31

      at Context.<anonymous> (test/unit/tree.test.ts:222:52)
      at processImmediate (node:internal/timers:478:21)

  2) findDiffDepthi
       expect diffi between 0 and 2147483648 to be 31:

      AssertionError: expected NaN to equal 31
      + expected - actual

      -NaN
      +31

      at Context.<anonymous> (test/unit/tree.test.ts:222:52)
      at processImmediate (node:internal/timers:478:21)

  3) findDiffDepthi
       expect diffi between 2147483647 and 2147483648 to be 31:

      AssertionError: expected -Infinity to equal 31
      + expected - actual

      --Infinity
      +31

      at Context.<anonymous> (test/unit/tree.test.ts:222:52)
      at processImmediate (node:internal/timers:478:21)

also it does not support >= 32 bits

Expected behavior

Steps to Reproduce

Run the above unit tests