Skip to content

Instantly share code, notes, and snippets.

@jordanorelli
Last active September 11, 2016 16:42
Show Gist options
  • Save jordanorelli/f782ea6fe89f5f53c425e0ce5d33abb7 to your computer and use it in GitHub Desktop.
Save jordanorelli/f782ea6fe89f5f53c425e0ce5d33abb7 to your computer and use it in GitHub Desktop.
0 {36271 0 PlusOne}
10 {25474 39 FieldPathEncodeFinish}
1110 {10334 1 PlusTwo}
1111 {10530 11 PushOneLeftDeltaNRightNonZeroPack6Bits}
11000 {2942 8 PushOneLeftDeltaOneRightNonZero}
11010 {4128 4 PlusN}
110010 {1375 2 PlusThree}
110011 {1837 29 PopAllButOnePlusOne}
11011001 {471 10 PushOneLeftDeltaNRightNonZero}
11011010 {521 7 PushOneLeftDeltaOneRightZero}
11011100 {560 9 PushOneLeftDeltaNRightZero}
11011110 {634 32 PopAllButOnePlusNPack6Bits}
11011111 {646 3 PlusFour}
110110000 {149 30 PopAllButOnePlusN}
110110110 {251 12 PushOneLeftDeltaNRightNonZeroPack8Bits}
110110111 {271 37 NonTopoPenultimatePlusOne}
110111010 {300 31 PopAllButOnePlusNPack3Bits}
110111011 {310 26 PushNAndNonTopological}
1101100010 {99 38 NonTopoComplexPack4Bits}
11011000111 {76 36 NonTopoComplex}
110110001101 {35 5 PushOneLeftDeltaZeroRightZero}
110110001100001 {2 27 PopOnePlusOne}
110110001100100 {3 6 PushOneLeftDeltaZeroRightNonZero}
1101100011000000 {1 23 PushThreeLeftDeltaN}
1101100011000001 {1 24 PushThreePack5LeftDeltaN}
1101100011000100 {1 25 PushN}
1101100011000101 {1 28 PopOnePlusN}
1101100011000110 {1 33 PopNPlusOne}
1101100011000111 {1 34 PopNPlusN}
1101100011001010 {1 35 PopNAndNonTopographical}
11011000110010110 {1 13 PushTwoLeftDeltaZero}
11011000110010111 {1 14 PushTwoPack5LeftDeltaZero}
11011000110011000 {1 15 PushThreeLeftDeltaZero}
11011000110011001 {1 16 PushThreePack5LeftDeltaZero}
11011000110011010 {1 17 PushTwoLeftDeltaOne}
11011000110011011 {1 18 PushTwoPack5LeftDeltaOne}
11011000110011100 {1 19 PushThreeLeftDeltaOne}
11011000110011101 {1 20 PushThreePack5LeftDeltaOne}
11011000110011110 {1 21 PushTwoLeftDeltaN}
11011000110011111 {1 22 PushTwoPack5LeftDeltaN}
@jordanorelli
Copy link
Author

the long runs of 0's seem deeply, deeply suspicious to me, but I guess in theory they could be correct.

@jordanorelli
Copy link
Author

giving every weight 0 item a weight of 1 (as manta does) yields an entirely different and much more sensible set of codes.

@invokr
Copy link

invokr commented Sep 8, 2016

The weights seem to be correct, I checked 3-4 of them randomly. Feel free to use this static lookup function:

/** Static fieldpath lookup */
force_inline fieldop* fieldop_lookup( uint32_t id ) {
    switch ( id ) {
    case 0: // PlusOne
        return &fieldpath_operations[0];
    case 2: // FieldPathEncodeFinish
        return &fieldpath_operations[39];
    case 14: // PlusTwo
        return &fieldpath_operations[1];
    case 15: // PushOneLeftDeltaNRightNonZeroPack6Bits
        return &fieldpath_operations[11];
    case 24: // PushOneLeftDeltaOneRightNonZero
        return &fieldpath_operations[8];
    case 26: // PlusN
        return &fieldpath_operations[4];
    case 50: // PlusThree
        return &fieldpath_operations[2];
    case 51: // PopAllButOnePlusOne
        return &fieldpath_operations[29];
    case 217: // PushOneLeftDeltaNRightNonZero
        return &fieldpath_operations[10];
    case 218: // PushOneLeftDeltaOneRightZero
        return &fieldpath_operations[7];
    case 220: // PushOneLeftDeltaNRightZero
        return &fieldpath_operations[9];
    case 222: // PopAllButOnePlusNPack6Bits
        return &fieldpath_operations[32];
    case 223: // PlusFour
        return &fieldpath_operations[3];
    case 432: // PopAllButOnePlusN
        return &fieldpath_operations[30];
    case 438: // PushOneLeftDeltaNRightNonZeroPack8Bits
        return &fieldpath_operations[12];
    case 439: // NonTopoPenultimatePlusOne
        return &fieldpath_operations[37];
    case 442: // PopAllButOnePlusNPack3Bits
        return &fieldpath_operations[31];
    case 443: // PushNAndNonTopological
        return &fieldpath_operations[26];
    case 866: // NonTopoComplexPack4Bits
        return &fieldpath_operations[38];
    case 1735: // NonTopoComplex
        return &fieldpath_operations[36];
    case 3469: // PushOneLeftDeltaZeroRightZero
        return &fieldpath_operations[5];
    case 27745: // PopOnePlusOne
        return &fieldpath_operations[27];
    case 27749: // PushOneLeftDeltaZeroRightNonZero
        return &fieldpath_operations[6];
    case 55488: // PopNAndNonTopographical
        return &fieldpath_operations[35];
    case 55489: // PopNPlusN
        return &fieldpath_operations[34];
    case 55492: // PushN
        return &fieldpath_operations[25];
    case 55493: // PushThreePack5LeftDeltaN
        return &fieldpath_operations[24];
    case 55494: // PopNPlusOne
        return &fieldpath_operations[33];
    case 55495: // PopOnePlusN
        return &fieldpath_operations[28];
    case 55496: // PushTwoLeftDeltaZero
        return &fieldpath_operations[13];
    case 110994: // PushThreeLeftDeltaZero
        return &fieldpath_operations[15];
    case 110995: // PushTwoPack5LeftDeltaZero
        return &fieldpath_operations[14];
    case 111000: // PushTwoLeftDeltaN
        return &fieldpath_operations[21];
    case 111001: // PushThreePack5LeftDeltaOne
        return &fieldpath_operations[20];
    case 111002: // PushThreeLeftDeltaN
        return &fieldpath_operations[23];
    case 111003: // PushTwoPack5LeftDeltaN
        return &fieldpath_operations[22];
    case 111004: // PushTwoLeftDeltaOne
        return &fieldpath_operations[17];
    case 111005: // PushThreePack5LeftDeltaZero
        return &fieldpath_operations[16];
    case 111006: // PushThreeLeftDeltaOne
        return &fieldpath_operations[19];
    case 111007: // PushTwoPack5LeftDeltaOne
        return &fieldpath_operations[18];
    default:
        return nullptr;
    }
}

@spheenik
Copy link

spheenik commented Sep 8, 2016

if you run this file it'll open a graph of the reconstructed huffman tree, containing all codes. (on linux!)

@spheenik
Copy link

spheenik commented Sep 8, 2016

Update: here it is!

@jordanorelli
Copy link
Author

@spheenik thanks! turns out my tree was slightly wrong, but I was able to correct it based on your graph. I wasn't counting the nodes as they were added to increment what you call "num"; for intermediate nodes I was just taking the largest of the leaf node's nums instead of assigning a new num to each intermediate nodes, which put a few things out of order at the bottom of the tree where all the leaf nodes have weights of zero.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment