rabin.c

/*
 * Copyright (c) 2015 Paul Arthur MacIain
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/* This is an implementation of the Rabin fingerprinting scheme, and returns
 * an unsigned 64 bit integer with a provably small chance of collision. The
 * fingerprint is not cryptographically secure.
 */

#include <config.h>

#include "rabin.h"

static uint64_t rh_lookup(uint64_t);

static uint64_t table32[ 256 ] = {
        0x0000000000000000,
        0x000000000000001b,
        0x0000000000000036,
        0x000000000000002d,
        0x000000000000006c,
        0x0000000000000077,
        0x000000000000005a,
        0x0000000000000041,
        0x00000000000000d8,
        0x00000000000000c3,
        0x00000000000000ee,
        0x00000000000000f5,
        0x00000000000000b4,
        0x00000000000000af,
        0x0000000000000082,
        0x0000000000000099,
        0x00000000000001b0,
        0x00000000000001ab,
        0x0000000000000186,
        0x000000000000019d,
        0x00000000000001dc,
        0x00000000000001c7,
        0x00000000000001ea,
        0x00000000000001f1,
        0x0000000000000168,
        0x0000000000000173,
        0x000000000000015e,
        0x0000000000000145,
        0x0000000000000104,
        0x000000000000011f,
        0x0000000000000132,
        0x0000000000000129,
        0x0000000000000360,
        0x000000000000037b,
        0x0000000000000356,
        0x000000000000034d,
        0x000000000000030c,
        0x0000000000000317,
        0x000000000000033a,
        0x0000000000000321,
        0x00000000000003b8,
        0x00000000000003a3,
        0x000000000000038e,
        0x0000000000000395,
        0x00000000000003d4,
        0x00000000000003cf,
        0x00000000000003e2,
        0x00000000000003f9,
        0x00000000000002d0,
        0x00000000000002cb,
        0x00000000000002e6,
        0x00000000000002fd,
        0x00000000000002bc,
        0x00000000000002a7,
        0x000000000000028a,
        0x0000000000000291,
        0x0000000000000208,
        0x0000000000000213,
        0x000000000000023e,
        0x0000000000000225,
        0x0000000000000264,
        0x000000000000027f,
        0x0000000000000252,
        0x0000000000000249,
        0x00000000000006c0,
        0x00000000000006db,
        0x00000000000006f6,
        0x00000000000006ed,
        0x00000000000006ac,
        0x00000000000006b7,
        0x000000000000069a,
        0x0000000000000681,
        0x0000000000000618,
        0x0000000000000603,
        0x000000000000062e,
        0x0000000000000635,
        0x0000000000000674,
        0x000000000000066f,
        0x0000000000000642,
        0x0000000000000659,
        0x0000000000000770,
        0x000000000000076b,
        0x0000000000000746,
        0x000000000000075d,
        0x000000000000071c,
        0x0000000000000707,
        0x000000000000072a,
        0x0000000000000731,
        0x00000000000007a8,
        0x00000000000007b3,
        0x000000000000079e,
        0x0000000000000785,
        0x00000000000007c4,
        0x00000000000007df,
        0x00000000000007f2,
        0x00000000000007e9,
        0x00000000000005a0,
        0x00000000000005bb,
        0x0000000000000596,
        0x000000000000058d,
        0x00000000000005cc,
        0x00000000000005d7,
        0x00000000000005fa,
        0x00000000000005e1,
        0x0000000000000578,
        0x0000000000000563,
        0x000000000000054e,
        0x0000000000000555,
        0x0000000000000514,
        0x000000000000050f,
        0x0000000000000522,
        0x0000000000000539,
        0x0000000000000410,
        0x000000000000040b,
        0x0000000000000426,
        0x000000000000043d,
        0x000000000000047c,
        0x0000000000000467,
        0x000000000000044a,
        0x0000000000000451,
        0x00000000000004c8,
        0x00000000000004d3,
        0x00000000000004fe,
        0x00000000000004e5,
        0x00000000000004a4,
        0x00000000000004bf,
        0x0000000000000492,
        0x0000000000000489,
        0x0000000000000d80,
        0x0000000000000d9b,
        0x0000000000000db6,
        0x0000000000000dad,
        0x0000000000000dec,
        0x0000000000000df7,
        0x0000000000000dda,
        0x0000000000000dc1,
        0x0000000000000d58,
        0x0000000000000d43,
        0x0000000000000d6e,
        0x0000000000000d75,
        0x0000000000000d34,
        0x0000000000000d2f,
        0x0000000000000d02,
        0x0000000000000d19,
        0x0000000000000c30,
        0x0000000000000c2b,
        0x0000000000000c06,
        0x0000000000000c1d,
        0x0000000000000c5c,
        0x0000000000000c47,
        0x0000000000000c6a,
        0x0000000000000c71,
        0x0000000000000ce8,
        0x0000000000000cf3,
        0x0000000000000cde,
        0x0000000000000cc5,
        0x0000000000000c84,
        0x0000000000000c9f,
        0x0000000000000cb2,
        0x0000000000000ca9,
        0x0000000000000ee0,
        0x0000000000000efb,
        0x0000000000000ed6,
        0x0000000000000ecd,
        0x0000000000000e8c,
        0x0000000000000e97,
        0x0000000000000eba,
        0x0000000000000ea1,
        0x0000000000000e38,
        0x0000000000000e23,
        0x0000000000000e0e,
        0x0000000000000e15,
        0x0000000000000e54,
        0x0000000000000e4f,
        0x0000000000000e62,
        0x0000000000000e79,
        0x0000000000000f50,
        0x0000000000000f4b,
        0x0000000000000f66,
        0x0000000000000f7d,
        0x0000000000000f3c,
        0x0000000000000f27,
        0x0000000000000f0a,
        0x0000000000000f11,
        0x0000000000000f88,
        0x0000000000000f93,
        0x0000000000000fbe,
        0x0000000000000fa5,
        0x0000000000000fe4,
        0x0000000000000fff,
        0x0000000000000fd2,
        0x0000000000000fc9,
        0x0000000000000b40,
        0x0000000000000b5b,
        0x0000000000000b76,
        0x0000000000000b6d,
        0x0000000000000b2c,
        0x0000000000000b37,
        0x0000000000000b1a,
        0x0000000000000b01,
        0x0000000000000b98,
        0x0000000000000b83,
        0x0000000000000bae,
        0x0000000000000bb5,
        0x0000000000000bf4,
        0x0000000000000bef,
        0x0000000000000bc2,
        0x0000000000000bd9,
        0x0000000000000af0,
        0x0000000000000aeb,
        0x0000000000000ac6,
        0x0000000000000add,
        0x0000000000000a9c,
        0x0000000000000a87,
        0x0000000000000aaa,
        0x0000000000000ab1,
        0x0000000000000a28,
        0x0000000000000a33,
        0x0000000000000a1e,
        0x0000000000000a05,
        0x0000000000000a44,
        0x0000000000000a5f,
        0x0000000000000a72,
        0x0000000000000a69,
        0x0000000000000820,
        0x000000000000083b,
        0x0000000000000816,
        0x000000000000080d,
        0x000000000000084c,
        0x0000000000000857,
        0x000000000000087a,
        0x0000000000000861,
        0x00000000000008f8,
        0x00000000000008e3,
        0x00000000000008ce,
        0x00000000000008d5,
        0x0000000000000894,
        0x000000000000088f,
        0x00000000000008a2,
        0x00000000000008b9,
        0x0000000000000990,
        0x000000000000098b,
        0x00000000000009a6,
        0x00000000000009bd,
        0x00000000000009fc,
        0x00000000000009e7,
        0x00000000000009ca,
        0x00000000000009d1,
        0x0000000000000948,
        0x0000000000000953,
        0x000000000000097e,
        0x0000000000000965,
        0x0000000000000924,
        0x000000000000093f,
        0x0000000000000912,
        0x0000000000000909,
};

static uint64_t table40[ 256 ] = {
        0x0000000000000000,
        0x0000000000001b00,
        0x0000000000003600,
        0x0000000000002d00,
        0x0000000000006c00,
        0x0000000000007700,
        0x0000000000005a00,
        0x0000000000004100,
        0x000000000000d800,
        0x000000000000c300,
        0x000000000000ee00,
        0x000000000000f500,
        0x000000000000b400,
        0x000000000000af00,
        0x0000000000008200,
        0x0000000000009900,
        0x000000000001b000,
        0x000000000001ab00,
        0x0000000000018600,
        0x0000000000019d00,
        0x000000000001dc00,
        0x000000000001c700,
        0x000000000001ea00,
        0x000000000001f100,
        0x0000000000016800,
        0x0000000000017300,
        0x0000000000015e00,
        0x0000000000014500,
        0x0000000000010400,
        0x0000000000011f00,
        0x0000000000013200,
        0x0000000000012900,
        0x0000000000036000,
        0x0000000000037b00,
        0x0000000000035600,
        0x0000000000034d00,
        0x0000000000030c00,
        0x0000000000031700,
        0x0000000000033a00,
        0x0000000000032100,
        0x000000000003b800,
        0x000000000003a300,
        0x0000000000038e00,
        0x0000000000039500,
        0x000000000003d400,
        0x000000000003cf00,
        0x000000000003e200,
        0x000000000003f900,
        0x000000000002d000,
        0x000000000002cb00,
        0x000000000002e600,
        0x000000000002fd00,
        0x000000000002bc00,
        0x000000000002a700,
        0x0000000000028a00,
        0x0000000000029100,
        0x0000000000020800,
        0x0000000000021300,
        0x0000000000023e00,
        0x0000000000022500,
        0x0000000000026400,
        0x0000000000027f00,
        0x0000000000025200,
        0x0000000000024900,
        0x000000000006c000,
        0x000000000006db00,
        0x000000000006f600,
        0x000000000006ed00,
        0x000000000006ac00,
        0x000000000006b700,
        0x0000000000069a00,
        0x0000000000068100,
        0x0000000000061800,
        0x0000000000060300,
        0x0000000000062e00,
        0x0000000000063500,
        0x0000000000067400,
        0x0000000000066f00,
        0x0000000000064200,
        0x0000000000065900,
        0x0000000000077000,
        0x0000000000076b00,
        0x0000000000074600,
        0x0000000000075d00,
        0x0000000000071c00,
        0x0000000000070700,
        0x0000000000072a00,
        0x0000000000073100,
        0x000000000007a800,
        0x000000000007b300,
        0x0000000000079e00,
        0x0000000000078500,
        0x000000000007c400,
        0x000000000007df00,
        0x000000000007f200,
        0x000000000007e900,
        0x000000000005a000,
        0x000000000005bb00,
        0x0000000000059600,
        0x0000000000058d00,
        0x000000000005cc00,
        0x000000000005d700,
        0x000000000005fa00,
        0x000000000005e100,
        0x0000000000057800,
        0x0000000000056300,
        0x0000000000054e00,
        0x0000000000055500,
        0x0000000000051400,
        0x0000000000050f00,
        0x0000000000052200,
        0x0000000000053900,
        0x0000000000041000,
        0x0000000000040b00,
        0x0000000000042600,
        0x0000000000043d00,
        0x0000000000047c00,
        0x0000000000046700,
        0x0000000000044a00,
        0x0000000000045100,
        0x000000000004c800,
        0x000000000004d300,
        0x000000000004fe00,
        0x000000000004e500,
        0x000000000004a400,
        0x000000000004bf00,
        0x0000000000049200,
        0x0000000000048900,
        0x00000000000d8000,
        0x00000000000d9b00,
        0x00000000000db600,
        0x00000000000dad00,
        0x00000000000dec00,
        0x00000000000df700,
        0x00000000000dda00,
        0x00000000000dc100,
        0x00000000000d5800,
        0x00000000000d4300,
        0x00000000000d6e00,
        0x00000000000d7500,
        0x00000000000d3400,
        0x00000000000d2f00,
        0x00000000000d0200,
        0x00000000000d1900,
        0x00000000000c3000,
        0x00000000000c2b00,
        0x00000000000c0600,
        0x00000000000c1d00,
        0x00000000000c5c00,
        0x00000000000c4700,
        0x00000000000c6a00,
        0x00000000000c7100,
        0x00000000000ce800,
        0x00000000000cf300,
        0x00000000000cde00,
        0x00000000000cc500,
        0x00000000000c8400,
        0x00000000000c9f00,
        0x00000000000cb200,
        0x00000000000ca900,
        0x00000000000ee000,
        0x00000000000efb00,
        0x00000000000ed600,
        0x00000000000ecd00,
        0x00000000000e8c00,
        0x00000000000e9700,
        0x00000000000eba00,
        0x00000000000ea100,
        0x00000000000e3800,
        0x00000000000e2300,
        0x00000000000e0e00,
        0x00000000000e1500,
        0x00000000000e5400,
        0x00000000000e4f00,
        0x00000000000e6200,
        0x00000000000e7900,
        0x00000000000f5000,
        0x00000000000f4b00,
        0x00000000000f6600,
        0x00000000000f7d00,
        0x00000000000f3c00,
        0x00000000000f2700,
        0x00000000000f0a00,
        0x00000000000f1100,
        0x00000000000f8800,
        0x00000000000f9300,
        0x00000000000fbe00,
        0x00000000000fa500,
        0x00000000000fe400,
        0x00000000000fff00,
        0x00000000000fd200,
        0x00000000000fc900,
        0x00000000000b4000,
        0x00000000000b5b00,
        0x00000000000b7600,
        0x00000000000b6d00,
        0x00000000000b2c00,
        0x00000000000b3700,
        0x00000000000b1a00,
        0x00000000000b0100,
        0x00000000000b9800,
        0x00000000000b8300,
        0x00000000000bae00,
        0x00000000000bb500,
        0x00000000000bf400,
        0x00000000000bef00,
        0x00000000000bc200,
        0x00000000000bd900,
        0x00000000000af000,
        0x00000000000aeb00,
        0x00000000000ac600,
        0x00000000000add00,
        0x00000000000a9c00,
        0x00000000000a8700,
        0x00000000000aaa00,
        0x00000000000ab100,
        0x00000000000a2800,
        0x00000000000a3300,
        0x00000000000a1e00,
        0x00000000000a0500,
        0x00000000000a4400,
        0x00000000000a5f00,
        0x00000000000a7200,
        0x00000000000a6900,
        0x0000000000082000,
        0x0000000000083b00,
        0x0000000000081600,
        0x0000000000080d00,
        0x0000000000084c00,
        0x0000000000085700,
        0x0000000000087a00,
        0x0000000000086100,
        0x000000000008f800,
        0x000000000008e300,
        0x000000000008ce00,
        0x000000000008d500,
        0x0000000000089400,
        0x0000000000088f00,
        0x000000000008a200,
        0x000000000008b900,
        0x0000000000099000,
        0x0000000000098b00,
        0x000000000009a600,
        0x000000000009bd00,
        0x000000000009fc00,
        0x000000000009e700,
        0x000000000009ca00,
        0x000000000009d100,
        0x0000000000094800,
        0x0000000000095300,
        0x0000000000097e00,
        0x0000000000096500,
        0x0000000000092400,
        0x0000000000093f00,
        0x0000000000091200,
        0x0000000000090900,
};

static uint64_t table48[ 256 ] = {
        0x0000000000000000,
        0x00000000001b0000,
        0x0000000000360000,
        0x00000000002d0000,
        0x00000000006c0000,
        0x0000000000770000,
        0x00000000005a0000,
        0x0000000000410000,
        0x0000000000d80000,
        0x0000000000c30000,
        0x0000000000ee0000,
        0x0000000000f50000,
        0x0000000000b40000,
        0x0000000000af0000,
        0x0000000000820000,
        0x0000000000990000,
        0x0000000001b00000,
        0x0000000001ab0000,
        0x0000000001860000,
        0x00000000019d0000,
        0x0000000001dc0000,
        0x0000000001c70000,
        0x0000000001ea0000,
        0x0000000001f10000,
        0x0000000001680000,
        0x0000000001730000,
        0x00000000015e0000,
        0x0000000001450000,
        0x0000000001040000,
        0x00000000011f0000,
        0x0000000001320000,
        0x0000000001290000,
        0x0000000003600000,
        0x00000000037b0000,
        0x0000000003560000,
        0x00000000034d0000,
        0x00000000030c0000,
        0x0000000003170000,
        0x00000000033a0000,
        0x0000000003210000,
        0x0000000003b80000,
        0x0000000003a30000,
        0x00000000038e0000,
        0x0000000003950000,
        0x0000000003d40000,
        0x0000000003cf0000,
        0x0000000003e20000,
        0x0000000003f90000,
        0x0000000002d00000,
        0x0000000002cb0000,
        0x0000000002e60000,
        0x0000000002fd0000,
        0x0000000002bc0000,
        0x0000000002a70000,
        0x00000000028a0000,
        0x0000000002910000,
        0x0000000002080000,
        0x0000000002130000,
        0x00000000023e0000,
        0x0000000002250000,
        0x0000000002640000,
        0x00000000027f0000,
        0x0000000002520000,
        0x0000000002490000,
        0x0000000006c00000,
        0x0000000006db0000,
        0x0000000006f60000,
        0x0000000006ed0000,
        0x0000000006ac0000,
        0x0000000006b70000,
        0x00000000069a0000,
        0x0000000006810000,
        0x0000000006180000,
        0x0000000006030000,
        0x00000000062e0000,
        0x0000000006350000,
        0x0000000006740000,
        0x00000000066f0000,
        0x0000000006420000,
        0x0000000006590000,
        0x0000000007700000,
        0x00000000076b0000,
        0x0000000007460000,
        0x00000000075d0000,
        0x00000000071c0000,
        0x0000000007070000,
        0x00000000072a0000,
        0x0000000007310000,
        0x0000000007a80000,
        0x0000000007b30000,
        0x00000000079e0000,
        0x0000000007850000,
        0x0000000007c40000,
        0x0000000007df0000,
        0x0000000007f20000,
        0x0000000007e90000,
        0x0000000005a00000,
        0x0000000005bb0000,
        0x0000000005960000,
        0x00000000058d0000,
        0x0000000005cc0000,
        0x0000000005d70000,
        0x0000000005fa0000,
        0x0000000005e10000,
        0x0000000005780000,
        0x0000000005630000,
        0x00000000054e0000,
        0x0000000005550000,
        0x0000000005140000,
        0x00000000050f0000,
        0x0000000005220000,
        0x0000000005390000,
        0x0000000004100000,
        0x00000000040b0000,
        0x0000000004260000,
        0x00000000043d0000,
        0x00000000047c0000,
        0x0000000004670000,
        0x00000000044a0000,
        0x0000000004510000,
        0x0000000004c80000,
        0x0000000004d30000,
        0x0000000004fe0000,
        0x0000000004e50000,
        0x0000000004a40000,
        0x0000000004bf0000,
        0x0000000004920000,
        0x0000000004890000,
        0x000000000d800000,
        0x000000000d9b0000,
        0x000000000db60000,
        0x000000000dad0000,
        0x000000000dec0000,
        0x000000000df70000,
        0x000000000dda0000,
        0x000000000dc10000,
        0x000000000d580000,
        0x000000000d430000,
        0x000000000d6e0000,
        0x000000000d750000,
        0x000000000d340000,
        0x000000000d2f0000,
        0x000000000d020000,
        0x000000000d190000,
        0x000000000c300000,
        0x000000000c2b0000,
        0x000000000c060000,
        0x000000000c1d0000,
        0x000000000c5c0000,
        0x000000000c470000,
        0x000000000c6a0000,
        0x000000000c710000,
        0x000000000ce80000,
        0x000000000cf30000,
        0x000000000cde0000,
        0x000000000cc50000,
        0x000000000c840000,
        0x000000000c9f0000,
        0x000000000cb20000,
        0x000000000ca90000,
        0x000000000ee00000,
        0x000000000efb0000,
        0x000000000ed60000,
        0x000000000ecd0000,
        0x000000000e8c0000,
        0x000000000e970000,
        0x000000000eba0000,
        0x000000000ea10000,
        0x000000000e380000,
        0x000000000e230000,
        0x000000000e0e0000,
        0x000000000e150000,
        0x000000000e540000,
        0x000000000e4f0000,
        0x000000000e620000,
        0x000000000e790000,
        0x000000000f500000,
        0x000000000f4b0000,
        0x000000000f660000,
        0x000000000f7d0000,
        0x000000000f3c0000,
        0x000000000f270000,
        0x000000000f0a0000,
        0x000000000f110000,
        0x000000000f880000,
        0x000000000f930000,
        0x000000000fbe0000,
        0x000000000fa50000,
        0x000000000fe40000,
        0x000000000fff0000,
        0x000000000fd20000,
        0x000000000fc90000,
        0x000000000b400000,
        0x000000000b5b0000,
        0x000000000b760000,
        0x000000000b6d0000,
        0x000000000b2c0000,
        0x000000000b370000,
        0x000000000b1a0000,
        0x000000000b010000,
        0x000000000b980000,
        0x000000000b830000,
        0x000000000bae0000,
        0x000000000bb50000,
        0x000000000bf40000,
        0x000000000bef0000,
        0x000000000bc20000,
        0x000000000bd90000,
        0x000000000af00000,
        0x000000000aeb0000,
        0x000000000ac60000,
        0x000000000add0000,
        0x000000000a9c0000,
        0x000000000a870000,
        0x000000000aaa0000,
        0x000000000ab10000,
        0x000000000a280000,
        0x000000000a330000,
        0x000000000a1e0000,
        0x000000000a050000,
        0x000000000a440000,
        0x000000000a5f0000,
        0x000000000a720000,
        0x000000000a690000,
        0x0000000008200000,
        0x00000000083b0000,
        0x0000000008160000,
        0x00000000080d0000,
        0x00000000084c0000,
        0x0000000008570000,
        0x00000000087a0000,
        0x0000000008610000,
        0x0000000008f80000,
        0x0000000008e30000,
        0x0000000008ce0000,
        0x0000000008d50000,
        0x0000000008940000,
        0x00000000088f0000,
        0x0000000008a20000,
        0x0000000008b90000,
        0x0000000009900000,
        0x00000000098b0000,
        0x0000000009a60000,
        0x0000000009bd0000,
        0x0000000009fc0000,
        0x0000000009e70000,
        0x0000000009ca0000,
        0x0000000009d10000,
        0x0000000009480000,
        0x0000000009530000,
        0x00000000097e0000,
        0x0000000009650000,
        0x0000000009240000,
        0x00000000093f0000,
        0x0000000009120000,
        0x0000000009090000,
};

static uint64_t table56[ 256 ] = {
        0x0000000000000000,
        0x000000001b000000,
        0x0000000036000000,
        0x000000002d000000,
        0x000000006c000000,
        0x0000000077000000,
        0x000000005a000000,
        0x0000000041000000,
        0x00000000d8000000,
        0x00000000c3000000,
        0x00000000ee000000,
        0x00000000f5000000,
        0x00000000b4000000,
        0x00000000af000000,
        0x0000000082000000,
        0x0000000099000000,
        0x00000001b0000000,
        0x00000001ab000000,
        0x0000000186000000,
        0x000000019d000000,
        0x00000001dc000000,
        0x00000001c7000000,
        0x00000001ea000000,
        0x00000001f1000000,
        0x0000000168000000,
        0x0000000173000000,
        0x000000015e000000,
        0x0000000145000000,
        0x0000000104000000,
        0x000000011f000000,
        0x0000000132000000,
        0x0000000129000000,
        0x0000000360000000,
        0x000000037b000000,
        0x0000000356000000,
        0x000000034d000000,
        0x000000030c000000,
        0x0000000317000000,
        0x000000033a000000,
        0x0000000321000000,
        0x00000003b8000000,
        0x00000003a3000000,
        0x000000038e000000,
        0x0000000395000000,
        0x00000003d4000000,
        0x00000003cf000000,
        0x00000003e2000000,
        0x00000003f9000000,
        0x00000002d0000000,
        0x00000002cb000000,
        0x00000002e6000000,
        0x00000002fd000000,
        0x00000002bc000000,
        0x00000002a7000000,
        0x000000028a000000,
        0x0000000291000000,
        0x0000000208000000,
        0x0000000213000000,
        0x000000023e000000,
        0x0000000225000000,
        0x0000000264000000,
        0x000000027f000000,
        0x0000000252000000,
        0x0000000249000000,
        0x00000006c0000000,
        0x00000006db000000,
        0x00000006f6000000,
        0x00000006ed000000,
        0x00000006ac000000,
        0x00000006b7000000,
        0x000000069a000000,
        0x0000000681000000,
        0x0000000618000000,
        0x0000000603000000,
        0x000000062e000000,
        0x0000000635000000,
        0x0000000674000000,
        0x000000066f000000,
        0x0000000642000000,
        0x0000000659000000,
        0x0000000770000000,
        0x000000076b000000,
        0x0000000746000000,
        0x000000075d000000,
        0x000000071c000000,
        0x0000000707000000,
        0x000000072a000000,
        0x0000000731000000,
        0x00000007a8000000,
        0x00000007b3000000,
        0x000000079e000000,
        0x0000000785000000,
        0x00000007c4000000,
        0x00000007df000000,
        0x00000007f2000000,
        0x00000007e9000000,
        0x00000005a0000000,
        0x00000005bb000000,
        0x0000000596000000,
        0x000000058d000000,
        0x00000005cc000000,
        0x00000005d7000000,
        0x00000005fa000000,
        0x00000005e1000000,
        0x0000000578000000,
        0x0000000563000000,
        0x000000054e000000,
        0x0000000555000000,
        0x0000000514000000,
        0x000000050f000000,
        0x0000000522000000,
        0x0000000539000000,
        0x0000000410000000,
        0x000000040b000000,
        0x0000000426000000,
        0x000000043d000000,
        0x000000047c000000,
        0x0000000467000000,
        0x000000044a000000,
        0x0000000451000000,
        0x00000004c8000000,
        0x00000004d3000000,
        0x00000004fe000000,
        0x00000004e5000000,
        0x00000004a4000000,
        0x00000004bf000000,
        0x0000000492000000,
        0x0000000489000000,
        0x0000000d80000000,
        0x0000000d9b000000,
        0x0000000db6000000,
        0x0000000dad000000,
        0x0000000dec000000,
        0x0000000df7000000,
        0x0000000dda000000,
        0x0000000dc1000000,
        0x0000000d58000000,
        0x0000000d43000000,
        0x0000000d6e000000,
        0x0000000d75000000,
        0x0000000d34000000,
        0x0000000d2f000000,
        0x0000000d02000000,
        0x0000000d19000000,
        0x0000000c30000000,
        0x0000000c2b000000,
        0x0000000c06000000,
        0x0000000c1d000000,
        0x0000000c5c000000,
        0x0000000c47000000,
        0x0000000c6a000000,
        0x0000000c71000000,
        0x0000000ce8000000,
        0x0000000cf3000000,
        0x0000000cde000000,
        0x0000000cc5000000,
        0x0000000c84000000,
        0x0000000c9f000000,
        0x0000000cb2000000,
        0x0000000ca9000000,
        0x0000000ee0000000,
        0x0000000efb000000,
        0x0000000ed6000000,
        0x0000000ecd000000,
        0x0000000e8c000000,
        0x0000000e97000000,
        0x0000000eba000000,
        0x0000000ea1000000,
        0x0000000e38000000,
        0x0000000e23000000,
        0x0000000e0e000000,
        0x0000000e15000000,
        0x0000000e54000000,
        0x0000000e4f000000,
        0x0000000e62000000,
        0x0000000e79000000,
        0x0000000f50000000,
        0x0000000f4b000000,
        0x0000000f66000000,
        0x0000000f7d000000,
        0x0000000f3c000000,
        0x0000000f27000000,
        0x0000000f0a000000,
        0x0000000f11000000,
        0x0000000f88000000,
        0x0000000f93000000,
        0x0000000fbe000000,
        0x0000000fa5000000,
        0x0000000fe4000000,
        0x0000000fff000000,
        0x0000000fd2000000,
        0x0000000fc9000000,
        0x0000000b40000000,
        0x0000000b5b000000,
        0x0000000b76000000,
        0x0000000b6d000000,
        0x0000000b2c000000,
        0x0000000b37000000,
        0x0000000b1a000000,
        0x0000000b01000000,
        0x0000000b98000000,
        0x0000000b83000000,
        0x0000000bae000000,
        0x0000000bb5000000,
        0x0000000bf4000000,
        0x0000000bef000000,
        0x0000000bc2000000,
        0x0000000bd9000000,
        0x0000000af0000000,
        0x0000000aeb000000,
        0x0000000ac6000000,
        0x0000000add000000,
        0x0000000a9c000000,
        0x0000000a87000000,
        0x0000000aaa000000,
        0x0000000ab1000000,
        0x0000000a28000000,
        0x0000000a33000000,
        0x0000000a1e000000,
        0x0000000a05000000,
        0x0000000a44000000,
        0x0000000a5f000000,
        0x0000000a72000000,
        0x0000000a69000000,
        0x0000000820000000,
        0x000000083b000000,
        0x0000000816000000,
        0x000000080d000000,
        0x000000084c000000,
        0x0000000857000000,
        0x000000087a000000,
        0x0000000861000000,
        0x00000008f8000000,
        0x00000008e3000000,
        0x00000008ce000000,
        0x00000008d5000000,
        0x0000000894000000,
        0x000000088f000000,
        0x00000008a2000000,
        0x00000008b9000000,
        0x0000000990000000,
        0x000000098b000000,
        0x00000009a6000000,
        0x00000009bd000000,
        0x00000009fc000000,
        0x00000009e7000000,
        0x00000009ca000000,
        0x00000009d1000000,
        0x0000000948000000,
        0x0000000953000000,
        0x000000097e000000,
        0x0000000965000000,
        0x0000000924000000,
        0x000000093f000000,
        0x0000000912000000,
        0x0000000909000000,
};

static uint64_t table64[ 256 ] = {
        0x0000000000000000,
        0x0000001b00000000,
        0x0000003600000000,
        0x0000002d00000000,
        0x0000006c00000000,
        0x0000007700000000,
        0x0000005a00000000,
        0x0000004100000000,
        0x000000d800000000,
        0x000000c300000000,
        0x000000ee00000000,
        0x000000f500000000,
        0x000000b400000000,
        0x000000af00000000,
        0x0000008200000000,
        0x0000009900000000,
        0x000001b000000000,
        0x000001ab00000000,
        0x0000018600000000,
        0x0000019d00000000,
        0x000001dc00000000,
        0x000001c700000000,
        0x000001ea00000000,
        0x000001f100000000,
        0x0000016800000000,
        0x0000017300000000,
        0x0000015e00000000,
        0x0000014500000000,
        0x0000010400000000,
        0x0000011f00000000,
        0x0000013200000000,
        0x0000012900000000,
        0x0000036000000000,
        0x0000037b00000000,
        0x0000035600000000,
        0x0000034d00000000,
        0x0000030c00000000,
        0x0000031700000000,
        0x0000033a00000000,
        0x0000032100000000,
        0x000003b800000000,
        0x000003a300000000,
        0x0000038e00000000,
        0x0000039500000000,
        0x000003d400000000,
        0x000003cf00000000,
        0x000003e200000000,
        0x000003f900000000,
        0x000002d000000000,
        0x000002cb00000000,
        0x000002e600000000,
        0x000002fd00000000,
        0x000002bc00000000,
        0x000002a700000000,
        0x0000028a00000000,
        0x0000029100000000,
        0x0000020800000000,
        0x0000021300000000,
        0x0000023e00000000,
        0x0000022500000000,
        0x0000026400000000,
        0x0000027f00000000,
        0x0000025200000000,
        0x0000024900000000,
        0x000006c000000000,
        0x000006db00000000,
        0x000006f600000000,
        0x000006ed00000000,
        0x000006ac00000000,
        0x000006b700000000,
        0x0000069a00000000,
        0x0000068100000000,
        0x0000061800000000,
        0x0000060300000000,
        0x0000062e00000000,
        0x0000063500000000,
        0x0000067400000000,
        0x0000066f00000000,
        0x0000064200000000,
        0x0000065900000000,
        0x0000077000000000,
        0x0000076b00000000,
        0x0000074600000000,
        0x0000075d00000000,
        0x0000071c00000000,
        0x0000070700000000,
        0x0000072a00000000,
        0x0000073100000000,
        0x000007a800000000,
        0x000007b300000000,
        0x0000079e00000000,
        0x0000078500000000,
        0x000007c400000000,
        0x000007df00000000,
        0x000007f200000000,
        0x000007e900000000,
        0x000005a000000000,
        0x000005bb00000000,
        0x0000059600000000,
        0x0000058d00000000,
        0x000005cc00000000,
        0x000005d700000000,
        0x000005fa00000000,
        0x000005e100000000,
        0x0000057800000000,
        0x0000056300000000,
        0x0000054e00000000,
        0x0000055500000000,
        0x0000051400000000,
        0x0000050f00000000,
        0x0000052200000000,
        0x0000053900000000,
        0x0000041000000000,
        0x0000040b00000000,
        0x0000042600000000,
        0x0000043d00000000,
        0x0000047c00000000,
        0x0000046700000000,
        0x0000044a00000000,
        0x0000045100000000,
        0x000004c800000000,
        0x000004d300000000,
        0x000004fe00000000,
        0x000004e500000000,
        0x000004a400000000,
        0x000004bf00000000,
        0x0000049200000000,
        0x0000048900000000,
        0x00000d8000000000,
        0x00000d9b00000000,
        0x00000db600000000,
        0x00000dad00000000,
        0x00000dec00000000,
        0x00000df700000000,
        0x00000dda00000000,
        0x00000dc100000000,
        0x00000d5800000000,
        0x00000d4300000000,
        0x00000d6e00000000,
        0x00000d7500000000,
        0x00000d3400000000,
        0x00000d2f00000000,
        0x00000d0200000000,
        0x00000d1900000000,
        0x00000c3000000000,
        0x00000c2b00000000,
        0x00000c0600000000,
        0x00000c1d00000000,
        0x00000c5c00000000,
        0x00000c4700000000,
        0x00000c6a00000000,
        0x00000c7100000000,
        0x00000ce800000000,
        0x00000cf300000000,
        0x00000cde00000000,
        0x00000cc500000000,
        0x00000c8400000000,
        0x00000c9f00000000,
        0x00000cb200000000,
        0x00000ca900000000,
        0x00000ee000000000,
        0x00000efb00000000,
        0x00000ed600000000,
        0x00000ecd00000000,
        0x00000e8c00000000,
        0x00000e9700000000,
        0x00000eba00000000,
        0x00000ea100000000,
        0x00000e3800000000,
        0x00000e2300000000,
        0x00000e0e00000000,
        0x00000e1500000000,
        0x00000e5400000000,
        0x00000e4f00000000,
        0x00000e6200000000,
        0x00000e7900000000,
        0x00000f5000000000,
        0x00000f4b00000000,
        0x00000f6600000000,
        0x00000f7d00000000,
        0x00000f3c00000000,
        0x00000f2700000000,
        0x00000f0a00000000,
        0x00000f1100000000,
        0x00000f8800000000,
        0x00000f9300000000,
        0x00000fbe00000000,
        0x00000fa500000000,
        0x00000fe400000000,
        0x00000fff00000000,
        0x00000fd200000000,
        0x00000fc900000000,
        0x00000b4000000000,
        0x00000b5b00000000,
        0x00000b7600000000,
        0x00000b6d00000000,
        0x00000b2c00000000,
        0x00000b3700000000,
        0x00000b1a00000000,
        0x00000b0100000000,
        0x00000b9800000000,
        0x00000b8300000000,
        0x00000bae00000000,
        0x00000bb500000000,
        0x00000bf400000000,
        0x00000bef00000000,
        0x00000bc200000000,
        0x00000bd900000000,
        0x00000af000000000,
        0x00000aeb00000000,
        0x00000ac600000000,
        0x00000add00000000,
        0x00000a9c00000000,
        0x00000a8700000000,
        0x00000aaa00000000,
        0x00000ab100000000,
        0x00000a2800000000,
        0x00000a3300000000,
        0x00000a1e00000000,
        0x00000a0500000000,
        0x00000a4400000000,
        0x00000a5f00000000,
        0x00000a7200000000,
        0x00000a6900000000,
        0x0000082000000000,
        0x0000083b00000000,
        0x0000081600000000,
        0x0000080d00000000,
        0x0000084c00000000,
        0x0000085700000000,
        0x0000087a00000000,
        0x0000086100000000,
        0x000008f800000000,
        0x000008e300000000,
        0x000008ce00000000,
        0x000008d500000000,
        0x0000089400000000,
        0x0000088f00000000,
        0x000008a200000000,
        0x000008b900000000,
        0x0000099000000000,
        0x0000098b00000000,
        0x000009a600000000,
        0x000009bd00000000,
        0x000009fc00000000,
        0x000009e700000000,
        0x000009ca00000000,
        0x000009d100000000,
        0x0000094800000000,
        0x0000095300000000,
        0x0000097e00000000,
        0x0000096500000000,
        0x0000092400000000,
        0x0000093f00000000,
        0x0000091200000000,
        0x0000090900000000,
};

static uint64_t table72[ 256 ] = {
        0x0000000000000000,
        0x00001b0000000000,
        0x0000360000000000,
        0x00002d0000000000,
        0x00006c0000000000,
        0x0000770000000000,
        0x00005a0000000000,
        0x0000410000000000,
        0x0000d80000000000,
        0x0000c30000000000,
        0x0000ee0000000000,
        0x0000f50000000000,
        0x0000b40000000000,
        0x0000af0000000000,
        0x0000820000000000,
        0x0000990000000000,
        0x0001b00000000000,
        0x0001ab0000000000,
        0x0001860000000000,
        0x00019d0000000000,
        0x0001dc0000000000,
        0x0001c70000000000,
        0x0001ea0000000000,
        0x0001f10000000000,
        0x0001680000000000,
        0x0001730000000000,
        0x00015e0000000000,
        0x0001450000000000,
        0x0001040000000000,
        0x00011f0000000000,
        0x0001320000000000,
        0x0001290000000000,
        0x0003600000000000,
        0x00037b0000000000,
        0x0003560000000000,
        0x00034d0000000000,
        0x00030c0000000000,
        0x0003170000000000,
        0x00033a0000000000,
        0x0003210000000000,
        0x0003b80000000000,
        0x0003a30000000000,
        0x00038e0000000000,
        0x0003950000000000,
        0x0003d40000000000,
        0x0003cf0000000000,
        0x0003e20000000000,
        0x0003f90000000000,
        0x0002d00000000000,
        0x0002cb0000000000,
        0x0002e60000000000,
        0x0002fd0000000000,
        0x0002bc0000000000,
        0x0002a70000000000,
        0x00028a0000000000,
        0x0002910000000000,
        0x0002080000000000,
        0x0002130000000000,
        0x00023e0000000000,
        0x0002250000000000,
        0x0002640000000000,
        0x00027f0000000000,
        0x0002520000000000,
        0x0002490000000000,
        0x0006c00000000000,
        0x0006db0000000000,
        0x0006f60000000000,
        0x0006ed0000000000,
        0x0006ac0000000000,
        0x0006b70000000000,
        0x00069a0000000000,
        0x0006810000000000,
        0x0006180000000000,
        0x0006030000000000,
        0x00062e0000000000,
        0x0006350000000000,
        0x0006740000000000,
        0x00066f0000000000,
        0x0006420000000000,
        0x0006590000000000,
        0x0007700000000000,
        0x00076b0000000000,
        0x0007460000000000,
        0x00075d0000000000,
        0x00071c0000000000,
        0x0007070000000000,
        0x00072a0000000000,
        0x0007310000000000,
        0x0007a80000000000,
        0x0007b30000000000,
        0x00079e0000000000,
        0x0007850000000000,
        0x0007c40000000000,
        0x0007df0000000000,
        0x0007f20000000000,
        0x0007e90000000000,
        0x0005a00000000000,
        0x0005bb0000000000,
        0x0005960000000000,
        0x00058d0000000000,
        0x0005cc0000000000,
        0x0005d70000000000,
        0x0005fa0000000000,
        0x0005e10000000000,
        0x0005780000000000,
        0x0005630000000000,
        0x00054e0000000000,
        0x0005550000000000,
        0x0005140000000000,
        0x00050f0000000000,
        0x0005220000000000,
        0x0005390000000000,
        0x0004100000000000,
        0x00040b0000000000,
        0x0004260000000000,
        0x00043d0000000000,
        0x00047c0000000000,
        0x0004670000000000,
        0x00044a0000000000,
        0x0004510000000000,
        0x0004c80000000000,
        0x0004d30000000000,
        0x0004fe0000000000,
        0x0004e50000000000,
        0x0004a40000000000,
        0x0004bf0000000000,
        0x0004920000000000,
        0x0004890000000000,
        0x000d800000000000,
        0x000d9b0000000000,
        0x000db60000000000,
        0x000dad0000000000,
        0x000dec0000000000,
        0x000df70000000000,
        0x000dda0000000000,
        0x000dc10000000000,
        0x000d580000000000,
        0x000d430000000000,
        0x000d6e0000000000,
        0x000d750000000000,
        0x000d340000000000,
        0x000d2f0000000000,
        0x000d020000000000,
        0x000d190000000000,
        0x000c300000000000,
        0x000c2b0000000000,
        0x000c060000000000,
        0x000c1d0000000000,
        0x000c5c0000000000,
        0x000c470000000000,
        0x000c6a0000000000,
        0x000c710000000000,
        0x000ce80000000000,
        0x000cf30000000000,
        0x000cde0000000000,
        0x000cc50000000000,
        0x000c840000000000,
        0x000c9f0000000000,
        0x000cb20000000000,
        0x000ca90000000000,
        0x000ee00000000000,
        0x000efb0000000000,
        0x000ed60000000000,
        0x000ecd0000000000,
        0x000e8c0000000000,
        0x000e970000000000,
        0x000eba0000000000,
        0x000ea10000000000,
        0x000e380000000000,
        0x000e230000000000,
        0x000e0e0000000000,
        0x000e150000000000,
        0x000e540000000000,
        0x000e4f0000000000,
        0x000e620000000000,
        0x000e790000000000,
        0x000f500000000000,
        0x000f4b0000000000,
        0x000f660000000000,
        0x000f7d0000000000,
        0x000f3c0000000000,
        0x000f270000000000,
        0x000f0a0000000000,
        0x000f110000000000,
        0x000f880000000000,
        0x000f930000000000,
        0x000fbe0000000000,
        0x000fa50000000000,
        0x000fe40000000000,
        0x000fff0000000000,
        0x000fd20000000000,
        0x000fc90000000000,
        0x000b400000000000,
        0x000b5b0000000000,
        0x000b760000000000,
        0x000b6d0000000000,
        0x000b2c0000000000,
        0x000b370000000000,
        0x000b1a0000000000,
        0x000b010000000000,
        0x000b980000000000,
        0x000b830000000000,
        0x000bae0000000000,
        0x000bb50000000000,
        0x000bf40000000000,
        0x000bef0000000000,
        0x000bc20000000000,
        0x000bd90000000000,
        0x000af00000000000,
        0x000aeb0000000000,
        0x000ac60000000000,
        0x000add0000000000,
        0x000a9c0000000000,
        0x000a870000000000,
        0x000aaa0000000000,
        0x000ab10000000000,
        0x000a280000000000,
        0x000a330000000000,
        0x000a1e0000000000,
        0x000a050000000000,
        0x000a440000000000,
        0x000a5f0000000000,
        0x000a720000000000,
        0x000a690000000000,
        0x0008200000000000,
        0x00083b0000000000,
        0x0008160000000000,
        0x00080d0000000000,
        0x00084c0000000000,
        0x0008570000000000,
        0x00087a0000000000,
        0x0008610000000000,
        0x0008f80000000000,
        0x0008e30000000000,
        0x0008ce0000000000,
        0x0008d50000000000,
        0x0008940000000000,
        0x00088f0000000000,
        0x0008a20000000000,
        0x0008b90000000000,
        0x0009900000000000,
        0x00098b0000000000,
        0x0009a60000000000,
        0x0009bd0000000000,
        0x0009fc0000000000,
        0x0009e70000000000,
        0x0009ca0000000000,
        0x0009d10000000000,
        0x0009480000000000,
        0x0009530000000000,
        0x00097e0000000000,
        0x0009650000000000,
        0x0009240000000000,
        0x00093f0000000000,
        0x0009120000000000,
        0x0009090000000000,
};

static uint64_t table80[ 256 ] = {
        0x0000000000000000,
        0x001b000000000000,
        0x0036000000000000,
        0x002d000000000000,
        0x006c000000000000,
        0x0077000000000000,
        0x005a000000000000,
        0x0041000000000000,
        0x00d8000000000000,
        0x00c3000000000000,
        0x00ee000000000000,
        0x00f5000000000000,
        0x00b4000000000000,
        0x00af000000000000,
        0x0082000000000000,
        0x0099000000000000,
        0x01b0000000000000,
        0x01ab000000000000,
        0x0186000000000000,
        0x019d000000000000,
        0x01dc000000000000,
        0x01c7000000000000,
        0x01ea000000000000,
        0x01f1000000000000,
        0x0168000000000000,
        0x0173000000000000,
        0x015e000000000000,
        0x0145000000000000,
        0x0104000000000000,
        0x011f000000000000,
        0x0132000000000000,
        0x0129000000000000,
        0x0360000000000000,
        0x037b000000000000,
        0x0356000000000000,
        0x034d000000000000,
        0x030c000000000000,
        0x0317000000000000,
        0x033a000000000000,
        0x0321000000000000,
        0x03b8000000000000,
        0x03a3000000000000,
        0x038e000000000000,
        0x0395000000000000,
        0x03d4000000000000,
        0x03cf000000000000,
        0x03e2000000000000,
        0x03f9000000000000,
        0x02d0000000000000,
        0x02cb000000000000,
        0x02e6000000000000,
        0x02fd000000000000,
        0x02bc000000000000,
        0x02a7000000000000,
        0x028a000000000000,
        0x0291000000000000,
        0x0208000000000000,
        0x0213000000000000,
        0x023e000000000000,
        0x0225000000000000,
        0x0264000000000000,
        0x027f000000000000,
        0x0252000000000000,
        0x0249000000000000,
        0x06c0000000000000,
        0x06db000000000000,
        0x06f6000000000000,
        0x06ed000000000000,
        0x06ac000000000000,
        0x06b7000000000000,
        0x069a000000000000,
        0x0681000000000000,
        0x0618000000000000,
        0x0603000000000000,
        0x062e000000000000,
        0x0635000000000000,
        0x0674000000000000,
        0x066f000000000000,
        0x0642000000000000,
        0x0659000000000000,
        0x0770000000000000,
        0x076b000000000000,
        0x0746000000000000,
        0x075d000000000000,
        0x071c000000000000,
        0x0707000000000000,
        0x072a000000000000,
        0x0731000000000000,
        0x07a8000000000000,
        0x07b3000000000000,
        0x079e000000000000,
        0x0785000000000000,
        0x07c4000000000000,
        0x07df000000000000,
        0x07f2000000000000,
        0x07e9000000000000,
        0x05a0000000000000,
        0x05bb000000000000,
        0x0596000000000000,
        0x058d000000000000,
        0x05cc000000000000,
        0x05d7000000000000,
        0x05fa000000000000,
        0x05e1000000000000,
        0x0578000000000000,
        0x0563000000000000,
        0x054e000000000000,
        0x0555000000000000,
        0x0514000000000000,
        0x050f000000000000,
        0x0522000000000000,
        0x0539000000000000,
        0x0410000000000000,
        0x040b000000000000,
        0x0426000000000000,
        0x043d000000000000,
        0x047c000000000000,
        0x0467000000000000,
        0x044a000000000000,
        0x0451000000000000,
        0x04c8000000000000,
        0x04d3000000000000,
        0x04fe000000000000,
        0x04e5000000000000,
        0x04a4000000000000,
        0x04bf000000000000,
        0x0492000000000000,
        0x0489000000000000,
        0x0d80000000000000,
        0x0d9b000000000000,
        0x0db6000000000000,
        0x0dad000000000000,
        0x0dec000000000000,
        0x0df7000000000000,
        0x0dda000000000000,
        0x0dc1000000000000,
        0x0d58000000000000,
        0x0d43000000000000,
        0x0d6e000000000000,
        0x0d75000000000000,
        0x0d34000000000000,
        0x0d2f000000000000,
        0x0d02000000000000,
        0x0d19000000000000,
        0x0c30000000000000,
        0x0c2b000000000000,
        0x0c06000000000000,
        0x0c1d000000000000,
        0x0c5c000000000000,
        0x0c47000000000000,
        0x0c6a000000000000,
        0x0c71000000000000,
        0x0ce8000000000000,
        0x0cf3000000000000,
        0x0cde000000000000,
        0x0cc5000000000000,
        0x0c84000000000000,
        0x0c9f000000000000,
        0x0cb2000000000000,
        0x0ca9000000000000,
        0x0ee0000000000000,
        0x0efb000000000000,
        0x0ed6000000000000,
        0x0ecd000000000000,
        0x0e8c000000000000,
        0x0e97000000000000,
        0x0eba000000000000,
        0x0ea1000000000000,
        0x0e38000000000000,
        0x0e23000000000000,
        0x0e0e000000000000,
        0x0e15000000000000,
        0x0e54000000000000,
        0x0e4f000000000000,
        0x0e62000000000000,
        0x0e79000000000000,
        0x0f50000000000000,
        0x0f4b000000000000,
        0x0f66000000000000,
        0x0f7d000000000000,
        0x0f3c000000000000,
        0x0f27000000000000,
        0x0f0a000000000000,
        0x0f11000000000000,
        0x0f88000000000000,
        0x0f93000000000000,
        0x0fbe000000000000,
        0x0fa5000000000000,
        0x0fe4000000000000,
        0x0fff000000000000,
        0x0fd2000000000000,
        0x0fc9000000000000,
        0x0b40000000000000,
        0x0b5b000000000000,
        0x0b76000000000000,
        0x0b6d000000000000,
        0x0b2c000000000000,
        0x0b37000000000000,
        0x0b1a000000000000,
        0x0b01000000000000,
        0x0b98000000000000,
        0x0b83000000000000,
        0x0bae000000000000,
        0x0bb5000000000000,
        0x0bf4000000000000,
        0x0bef000000000000,
        0x0bc2000000000000,
        0x0bd9000000000000,
        0x0af0000000000000,
        0x0aeb000000000000,
        0x0ac6000000000000,
        0x0add000000000000,
        0x0a9c000000000000,
        0x0a87000000000000,
        0x0aaa000000000000,
        0x0ab1000000000000,
        0x0a28000000000000,
        0x0a33000000000000,
        0x0a1e000000000000,
        0x0a05000000000000,
        0x0a44000000000000,
        0x0a5f000000000000,
        0x0a72000000000000,
        0x0a69000000000000,
        0x0820000000000000,
        0x083b000000000000,
        0x0816000000000000,
        0x080d000000000000,
        0x084c000000000000,
        0x0857000000000000,
        0x087a000000000000,
        0x0861000000000000,
        0x08f8000000000000,
        0x08e3000000000000,
        0x08ce000000000000,
        0x08d5000000000000,
        0x0894000000000000,
        0x088f000000000000,
        0x08a2000000000000,
        0x08b9000000000000,
        0x0990000000000000,
        0x098b000000000000,
        0x09a6000000000000,
        0x09bd000000000000,
        0x09fc000000000000,
        0x09e7000000000000,
        0x09ca000000000000,
        0x09d1000000000000,
        0x0948000000000000,
        0x0953000000000000,
        0x097e000000000000,
        0x0965000000000000,
        0x0924000000000000,
        0x093f000000000000,
        0x0912000000000000,
        0x0909000000000000,
};

static uint64_t table88[ 256 ] = {
        0x0000000000000000,
        0x1b00000000000000,
        0x3600000000000000,
        0x2d00000000000000,
        0x6c00000000000000,
        0x7700000000000000,
        0x5a00000000000000,
        0x4100000000000000,
        0xd800000000000000,
        0xc300000000000000,
        0xee00000000000000,
        0xf500000000000000,
        0xb400000000000000,
        0xaf00000000000000,
        0x8200000000000000,
        0x9900000000000000,
        0xb00000000000001b,
        0xab0000000000001b,
        0x860000000000001b,
        0x9d0000000000001b,
        0xdc0000000000001b,
        0xc70000000000001b,
        0xea0000000000001b,
        0xf10000000000001b,
        0x680000000000001b,
        0x730000000000001b,
        0x5e0000000000001b,
        0x450000000000001b,
        0x040000000000001b,
        0x1f0000000000001b,
        0x320000000000001b,
        0x290000000000001b,
        0x600000000000002d,
        0x7b0000000000002d,
        0x560000000000002d,
        0x4d0000000000002d,
        0x0c0000000000002d,
        0x170000000000002d,
        0x3a0000000000002d,
        0x210000000000002d,
        0xb80000000000002d,
        0xa30000000000002d,
        0x8e0000000000002d,
        0x950000000000002d,
        0xd40000000000002d,
        0xcf0000000000002d,
        0xe20000000000002d,
        0xf90000000000002d,
        0xd000000000000036,
        0xcb00000000000036,
        0xe600000000000036,
        0xfd00000000000036,
        0xbc00000000000036,
        0xa700000000000036,
        0x8a00000000000036,
        0x9100000000000036,
        0x0800000000000036,
        0x1300000000000036,
        0x3e00000000000036,
        0x2500000000000036,
        0x6400000000000036,
        0x7f00000000000036,
        0x5200000000000036,
        0x4900000000000036,
        0xc00000000000005a,
        0xdb0000000000005a,
        0xf60000000000005a,
        0xed0000000000005a,
        0xac0000000000005a,
        0xb70000000000005a,
        0x9a0000000000005a,
        0x810000000000005a,
        0x180000000000005a,
        0x030000000000005a,
        0x2e0000000000005a,
        0x350000000000005a,
        0x740000000000005a,
        0x6f0000000000005a,
        0x420000000000005a,
        0x590000000000005a,
        0x7000000000000041,
        0x6b00000000000041,
        0x4600000000000041,
        0x5d00000000000041,
        0x1c00000000000041,
        0x0700000000000041,
        0x2a00000000000041,
        0x3100000000000041,
        0xa800000000000041,
        0xb300000000000041,
        0x9e00000000000041,
        0x8500000000000041,
        0xc400000000000041,
        0xdf00000000000041,
        0xf200000000000041,
        0xe900000000000041,
        0xa000000000000077,
        0xbb00000000000077,
        0x9600000000000077,
        0x8d00000000000077,
        0xcc00000000000077,
        0xd700000000000077,
        0xfa00000000000077,
        0xe100000000000077,
        0x7800000000000077,
        0x6300000000000077,
        0x4e00000000000077,
        0x5500000000000077,
        0x1400000000000077,
        0x0f00000000000077,
        0x2200000000000077,
        0x3900000000000077,
        0x100000000000006c,
        0x0b0000000000006c,
        0x260000000000006c,
        0x3d0000000000006c,
        0x7c0000000000006c,
        0x670000000000006c,
        0x4a0000000000006c,
        0x510000000000006c,
        0xc80000000000006c,
        0xd30000000000006c,
        0xfe0000000000006c,
        0xe50000000000006c,
        0xa40000000000006c,
        0xbf0000000000006c,
        0x920000000000006c,
        0x890000000000006c,
        0x80000000000000af,
        0x9b000000000000af,
        0xb6000000000000af,
        0xad000000000000af,
        0xec000000000000af,
        0xf7000000000000af,
        0xda000000000000af,
        0xc1000000000000af,
        0x58000000000000af,
        0x43000000000000af,
        0x6e000000000000af,
        0x75000000000000af,
        0x34000000000000af,
        0x2f000000000000af,
        0x02000000000000af,
        0x19000000000000af,
        0x30000000000000b4,
        0x2b000000000000b4,
        0x06000000000000b4,
        0x1d000000000000b4,
        0x5c000000000000b4,
        0x47000000000000b4,
        0x6a000000000000b4,
        0x71000000000000b4,
        0xe8000000000000b4,
        0xf3000000000000b4,
        0xde000000000000b4,
        0xc5000000000000b4,
        0x84000000000000b4,
        0x9f000000000000b4,
        0xb2000000000000b4,
        0xa9000000000000b4,
        0xe000000000000082,
        0xfb00000000000082,
        0xd600000000000082,
        0xcd00000000000082,
        0x8c00000000000082,
        0x9700000000000082,
        0xba00000000000082,
        0xa100000000000082,
        0x3800000000000082,
        0x2300000000000082,
        0x0e00000000000082,
        0x1500000000000082,
        0x5400000000000082,
        0x4f00000000000082,
        0x6200000000000082,
        0x7900000000000082,
        0x5000000000000099,
        0x4b00000000000099,
        0x6600000000000099,
        0x7d00000000000099,
        0x3c00000000000099,
        0x2700000000000099,
        0x0a00000000000099,
        0x1100000000000099,
        0x8800000000000099,
        0x9300000000000099,
        0xbe00000000000099,
        0xa500000000000099,
        0xe400000000000099,
        0xff00000000000099,
        0xd200000000000099,
        0xc900000000000099,
        0x40000000000000f5,
        0x5b000000000000f5,
        0x76000000000000f5,
        0x6d000000000000f5,
        0x2c000000000000f5,
        0x37000000000000f5,
        0x1a000000000000f5,
        0x01000000000000f5,
        0x98000000000000f5,
        0x83000000000000f5,
        0xae000000000000f5,
        0xb5000000000000f5,
        0xf4000000000000f5,
        0xef000000000000f5,
        0xc2000000000000f5,
        0xd9000000000000f5,
        0xf0000000000000ee,
        0xeb000000000000ee,
        0xc6000000000000ee,
        0xdd000000000000ee,
        0x9c000000000000ee,
        0x87000000000000ee,
        0xaa000000000000ee,
        0xb1000000000000ee,
        0x28000000000000ee,
        0x33000000000000ee,
        0x1e000000000000ee,
        0x05000000000000ee,
        0x44000000000000ee,
        0x5f000000000000ee,
        0x72000000000000ee,
        0x69000000000000ee,
        0x20000000000000d8,
        0x3b000000000000d8,
        0x16000000000000d8,
        0x0d000000000000d8,
        0x4c000000000000d8,
        0x57000000000000d8,
        0x7a000000000000d8,
        0x61000000000000d8,
        0xf8000000000000d8,
        0xe3000000000000d8,
        0xce000000000000d8,
        0xd5000000000000d8,
        0x94000000000000d8,
        0x8f000000000000d8,
        0xa2000000000000d8,
        0xb9000000000000d8,
        0x90000000000000c3,
        0x8b000000000000c3,
        0xa6000000000000c3,
        0xbd000000000000c3,
        0xfc000000000000c3,
        0xe7000000000000c3,
        0xca000000000000c3,
        0xd1000000000000c3,
        0x48000000000000c3,
        0x53000000000000c3,
        0x7e000000000000c3,
        0x65000000000000c3,
        0x24000000000000c3,
        0x3f000000000000c3,
        0x12000000000000c3,
        0x09000000000000c3,
};


static uint64_t
rh_lookup(uint64_t rh) {
    return table32[ rh & 0xff ] ^ table40[ (rh >> 8) & 0xff ] ^
           table48[ (rh >> 16) & 0xff ] ^ table56[ (rh >> 24) & 0xff ] ^
           table64[ (rh >> 32) & 0xff ] ^ table72[ (rh >> 40) & 0xff ] ^
           table80[ (rh >> 48) & 0xff ] ^ table88[ (rh >> 56) & 0xff ];
}

uint64_t
rabin_fingerprint(const char *s, size_t len) {
    uint64_t rh = 0;
    int      i;

    for (i = 0; i < (len % 8); i++) {
        rh = (rh << 8) ^ (s[ i ] & 0xff);
    }

    for (; i < len; i += 8) {
        rh = rh_lookup(rh) ^ ((uint64_t)s[ i ] << 56) ^
             ((uint64_t)(s[ i + 1 ] & 0xff) << 48) ^
             ((uint64_t)(s[ i + 2 ] & 0xff) << 40) ^
             ((uint64_t)(s[ i + 3 ] & 0xff) << 32) ^
             ((uint64_t)(s[ i + 4 ] & 0xff) << 24) ^
             ((uint64_t)(s[ i + 5 ] & 0xff) << 16) ^
             ((uint64_t)(s[ i + 6 ] & 0xff) << 8) ^
             ((uint64_t)s[ i + 7 ] & 0xff);
    }

    return rh;
}