#include <stdint.h>

//=============================================
// rolling hash over 64-byte local area
// RollHash() rolls bytes in to the hash
//  they are implicitly rolled out by the top of the machine word

#if 1

// table-lookup hash :
extern const uint64_t c_hash_values_table64[256];
#define RollHash(h,ptr) ( ((h)<<1) + c_hash_values_table64[*(ptr)] )

#else

// multiplicative hash : (multiplier must be even)
#define RollHash(h,ptr) (((h)+(*(ptr))+271828182ULL)*(1865811235122147682ULL))

#endif

#define ROLLING_HASH_INIT   0xBF58476D1CE4E5B2ULL
//#define ROLLING_HASH_INIT 0

//=============================================

// find a content-determined boundary in [start,end)
//  returns nullptr if no boundary could be found
const uint8_t * FindBoundary(const uint8_t * start,const uint8_t * end,int64_t desired_fragment_len_log2)
{
    const int64_t desired_fragment_len = 1LL<<desired_fragment_len_log2;

    // desired_fragment_len should be well over 64 because we use a 64-byte window window to find boundaries
    //  probably 256 is the functional minimum

    const uint64_t fragment_boundary_mask = (~0ULL) << (64 - desired_fragment_len_log2); // high bits
    
    // fragment_len_min as large as possible helps speed
    //  fragment_len_min = 1/4 is good for speed and seems to be okay for quality
    // fragment_len_max as low as possible is important for speed
    const int64_t fragment_len_min = desired_fragment_len/4;
    const int64_t fragment_len_max = desired_fragment_len*4;

    if ( (end - start) < fragment_len_min )
    {
        // too short, no boundary
        return nullptr;
    }

    if ( (end - start) > fragment_len_max )
    {
        end = start + fragment_len_max;
    }

    // jump ahead by fragment_len_min
    const uint8_t * ptr = start + fragment_len_min;
        
    uint64_t min_hash_val = ~0ULL;
    const uint8_t * min_hash_ptr = nullptr;

    uint64_t h = ROLLING_HASH_INIT;
    
    // note: you could roll in the bytes in [0,fragment_len_min) to seed hash
    //  in my tests, doing so has no benefit to quality

    while ( ptr < end )
    {
        h = RollHash(h,ptr);
        
        if ( h < min_hash_val )
        {
            // fragment_boundary_mask is the high bits
            // could also do this as h <= ~fragment_boundary_mask
            //  but &==0 is just TEST
            // using the h <= threshold method would allow desired_fragment_len non-power-of-2
            if ( (h & fragment_boundary_mask) == 0 )
            {
                return ptr; // natural boundary!
            }
        
            min_hash_val = h;
            min_hash_ptr = ptr;
        }

        ptr++;
    }

    // natural cut was not found before end
    // put a cut at the location of min hash val
    
    if ( min_hash_ptr != nullptr )
    {
        // Boundary at location of min hash :
        return min_hash_ptr;
    }
    else
    {
        return nullptr;
    }
}

//============================================================

const uint64_t c_hash_values_table64[256] = 
{
    0x651748F5A15F8222, 0xD6EDA276C877D8EA, 0x66896EF9591B326B,
    0xCD97506B21370A12, 0x8C9C5C9ACBEB2A05, 0xB8B9553EE17665EF,
    0x1784A989315B1DE6, 0x947666C9C50DF4BD, 0xB3F660EA7FF2D6A4,
    0xBCD6ADB8D6D70EB5, 0xB0909464F9C63538, 0xE50E3E46A8E1B285,
    0x21ED7B80C0163CE0, 0xF209ACD115F7B43B, 0xB8C9CB07EAF16A58,
    0xB60478AA97BA854C, 0x8FB213A0B5654C3D, 0x42E8E7BD9FB03710,
    0x737E3DE60A90B54F, 0x9172885F5AA79C8B, 0x787FAAE7BE109C36,
    0x86AD156F5274CB9F, 0x6AC0A8DAA59EE1AB, 0x5E55BC229D5C618E,
    0xA54FB69A5F181D41, 0xC433D4CF44D8E974, 0xD9EFE85B722E48A3,
    0x7A5E64F9EA3D9759, 0xBA3771E13186015D, 0x5D468C5FAD6EF629,
    0x96B1AF02152EBFDE, 0x63706F4AA70E0111, 0xE7A9169252DE4749,
    0xF548D62570BC8329, 0xEE639A9117E8C946, 0xD31B0F46F3FF6847,
    0xFED7938495624FC5, 0x1EF2271C5A28122E, 0x7FD8E0E95EAC73EF,
    0x920558E0EE131D4C, 0xCE2E67CB1034BCD1, 0x6F4B338D34B004AE,
    0x92F5E7271CF95C9A, 0x12E1305A9C558342, 0x1E30D88013AD77AE,
    0x09ACC1A57BBB604E, 0xAF187082C6F56192, 0xD2E5D987F04AC6F0,
    0x3B22FCA40423DA70, 0x7DFBA8CE699A9A87, 0xE8B15F90EA96BD2A,
    0xCDA1A1089CC2CBE7, 0x72F70448459DE898, 0x1AB992DBB61CD46E,
    0x912AD04BECBB29DA, 0x98C6BB3AA3CE09ED, 0x6373BD2E7A041F3A,
    0x1F98F28BD178C53A, 0xE6ADBC82BA5D9F96, 0x7456DA7D805CBE01,
    0xD673662DCC135EEB, 0xB299E26EAADCB311, 0x2C2582172F8114AF,
    0xEDED114D7F623DA6, 0xB3462A0E623276E4, 0x3AF752BE3D34BFAA,
    0x1311CCC0A1855A89, 0x0812BBCECC92B2E4, 0x9974B5747289F2F5,
    0x3A030EFF770F2026, 0x52462B2AA42A847A, 0x2BEAA107D15A012B,
    0x0C0035E0FE073398, 0x4F2F9DE2AC206766, 0x5DD51A617C291DEB,
    0x1AC66905652CC03B, 0x11067B0947FC07A1, 0x02B5FCD96AD06D52,
    0x74244EC1AA2821FD, 0xF6089E32060E9439, 0xD8F076A33BCBF1A7,
    0x5162743C755D8D5E, 0x8D34FC683E4E3D06, 0x46EFE9B21A0252A3,
    0x4631E8D0109C6145, 0xFDF7A14BC0223957, 0x750934B3D0B8BB1E,
    0x2ECD1B3EFED5DDB9, 0x2BCBD89A83CCFBCE, 0x3507C79E58DD5886,
    0x5476A67ECD4A772F, 0xAA0BE3856DD76405, 0x22289A358A4DD421,
    0xF570433F14503AD1, 0x8A9F440251A722C3, 0x77DD711752B4398C,
    0xBBD9EDF9C6160A31, 0xB94B59220B23F079, 0xFDCA3D75D2F33CCF,
    0xB29452C460C9E977, 0xE89AFE2DD4BF3B02, 0x47EC6F32C91BFEE4,
    0x1AAB5EC3445706B8, 0x588BF4FA55334006, 0xE2290CA1E29ACD96,
    0x3C49E189F831C37C, 0x6448C973B5177498, 0x556A6E09BA158DE7,
    0x90B25013A8D9A067, 0xA4F2F7A50C58E1C4, 0x5E765E871008700E,
    0x242F5AE7738327AF, 0xC1E6A2819CC5A219, 0xCB48D801FD6A5449,
    0xA208DE2301931383, 0xDE3C143FE44E39B0, 0x6BB74B09C73E4133,
    0xB5B1ED1B63D54C11, 0x587567D454CE7716, 0xF47DDBC987CB0392,
    0x87B19254448F03F1, 0x985FD00EC372FAFA, 0x64B92BA521AA46E4,
    0xCE63F4013D587B0F, 0xA691AE698726030E, 0xEAEFBF690264E9AA,
    0x68EDD400523EB152, 0x35D9353AA1957C60, 0x2E2C2D7A9CB68385,
    0xFC7549EDAF43BF9E, 0x48B2ADB23026E2C7, 0x3777CB79A024BCF9,
    0x644128F7C184102D, 0x70189D3CA4390DE9, 0x085FEA7986D4CD34,
    0x6DBE7626C8457464, 0x9FA41CFA9C4265EB, 0xDAA163A641946463,
    0x02F5C4BD9EFA2074, 0x783201871822C3C9, 0xB0DFEC499202BCE0,
    0x1F1C9C12D84DCCAB, 0x1596F8819F2ED68E, 0xB0352C3E9FC84468,
    0x24A6673DB9122956, 0x84F5B9E60B274739, 0x7216B28A0B54AC46,
    0xC7789DE20E9CDCA4, 0x903DB5D289DD6563, 0xCE66A947F7033516,
    0x3677DBC62307B2CA, 0x8D8E9D5530EB46AC, 0x79C4BAD281BD93E2,
    0x287D942042068C36, 0xDE4B98E5464B6AD5, 0x612534B97D1D21BF,
    0xDF98659772D822A1, 0x93053DF791AA6264, 0x2254A8A2D54528BA,
    0x2301164AEB69C43D, 0xF56863474AC2417F, 0x6136B73E1B75DE42,
    0xC7C3BD487E06B532, 0x7232FBED1EB9BE85, 0x36D60F0BD7909E43,
    0xE08CBF774A4CE1F2, 0xF75FBC0D97CB8384, 0xA5097E5AF367637B,
    0x7BCE2DCFA856DBB2, 0xFBFB729DD808C894, 0x3DC8EBA10AD7112E,
    0xF2D1854EEDCE4928, 0xB705F5C1AEBD2104, 0x78FA4D004417D956,
    0x9E5162660729F858, 0xDA0BCD5EB9F91F0E, 0x748D1BE11E06B362,
    0xF4C2BE9A04547734, 0x6F2BCD7C88ABDF9A, 0x50865DAFDFD8A404,
    0x9D820665691728F0, 0x59FE7A56AA07118E, 0x4DF1D768C23660EC,
    0xAB6310B8EDFB8C5E, 0x029B47623FC9FFE4, 0x50C2CCA231374860,
    0x0561505A8DBBDC69, 0x8D07FE136DE385F3, 0xC7FB6BB1731B1C1C,
    0x2496D1256F1FAC7A, 0x79508CEE90D84273, 0x09F51A2108676501,
    0x2EF72D3DC6A50061, 0xE4AD98F5792DD6D6, 0x69FA05E609AE7D33,
    0xF7F30A8B9AE54285, 0x04A2CB6A0744764B, 0xC4B0762F39679435,
    0x60401BC93EF6047B, 0x76F6AA76E23DBE0C, 0x8A209197811E39DA,
    0x4489A9683FA03888, 0x2604AD5741A6F8D8, 0x7FAA9E0C64A94532,
    0x0DBFEE8CDAE8F54E, 0x0A7C5885F0B76D4A, 0x55DFB1AC12E83645,
    0xEDC967651C4938CC, 0x4E006AB71A48B85E, 0x193F621602DE413C,
    0xB56458B71D56944F, 0xF2B639509A2FA5DA, 0xB4A76F284C365450,
    0x4D3B65D2D2AE22F7, 0xBCC5F8303EFCA485, 0x8A044F312671AAEA,
    0x688D69E89AF0F57A, 0x229957DC1FACEDE8, 0x2ED75C321073DA13,
    0xF199E7ECE5FCEFEF, 0x50C85B5C837A6C64, 0x71703C6E676BF698,
    0xC1B4EB52B1E5A518, 0x0F46A5E6C9CB68CA, 0xEBB933688D69D7F7,
    0x5AB7404B8D1E3EF4, 0x261ACC20C5A64A90, 0xB88788798ADC718A,
    0x3E44E9B6BAD5BC15, 0xF6BB456F086346BC, 0xD66E17E5734CBDE1,
    0x392036DAE96E389D, 0x4A62CEAC9D4202DE, 0x9D55F412F32E5F6E,
    0x0E1D841509D9EE9D, 0xC3130BDC638ED9E2, 0x0CD0E82AF24964D9,
    0x3EC4C59463BA9B50, 0x055BC4D8685AB1BC, 0xB9E343C96A3A4253,
    0x8EBA190D8688F7F9, 0xD31DF36C792C629B, 0xDDF82F659B127104,
    0x6F12DC8BA930FBB7, 0xA0AEE6BB7E81A7F0, 0x8C6BA78747AE8777,
    0x86F00167EDA1F9BC, 0x3A6F8B8F8A3790C9, 0x7845BB4A1C3BFBBB,
    0xC875AB077F66CF23, 0xA68B83D8D69B97EE, 0xB967199139F9A0A6,
    0x8A3A1A4D3DE036B7, 0xDF3C5C0C017232A4, 0x8E60E63156990620,
    0xD31B4B03145F02FA
};

//====================================================================