/* From BorgBackup:
 * Copyright (C) 2015-2022 The Borg Collective (see AUTHORS file)
 * Copyright (C) 2010-2014 Jonas Borgström <jonas@borgstrom.se>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 * 3. The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior
 *    written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include <string.h> /* size_t */
#include <limb/int.h>

size_t
nextsplit(size_t min, size_t avg, const void *data, size_t dlen)
{
    if (dlen <= min) return dlen;
    u32 T[] =
    {
        0XE7F831EC, 0XF4026465, 0XAFB50CAE, 0X6D553C7A, 0XD639EFE3, 0X19A7B895, 0X9ABA5B21, 0X5417D6D4,
        0X35FD2B84, 0XD1F6A159, 0X3F8E323F, 0XB419551C, 0XF444CEBF, 0X21DC3B80, 0XDE8D1E36, 0X84A32436,
        0XBEB35A9D, 0XA36F24AA, 0XA4E60186, 0X98D18FFE, 0X3F042F9E, 0XDB228BCD, 0X096474B7, 0X5C20C2F7,
        0XF9EEC872, 0XE8625275, 0XB9D38F80, 0XD48EB716, 0X22A950B4, 0X3CBAAEAA, 0XC37CDDD3, 0X8FEA6F6A,
        0X1D55D526, 0X7FD6D3B3, 0XDAA072EE, 0X4345AC40, 0XA077C642, 0X8F2BD45B, 0X28509110, 0X55557613,
        0XFFC17311, 0XD961FFEF, 0XE532C287, 0XAAB95937, 0X46D38365, 0XB065C703, 0XF2D91D0F, 0X92CD4BB0,
        0X4007C712, 0XF35509DD, 0X505B2F69, 0X557EAD81, 0X310F4563, 0XBDDC5BE8, 0X9760F38C, 0X701E0205,
        0X00157244, 0X14912826, 0XDC4CA32B, 0X67B196DE, 0X5DB292E8, 0X8C1B406B, 0X01F34075, 0XFA2520F7,
        0X73BC37AB, 0X1E18BC30, 0XFE2C6CB3, 0X20C522D0, 0X5639E3DB, 0X942BDA35, 0X899AF9D1, 0XCED44035,
        0X98CC025B, 0X255F5771, 0X70FEFA24, 0XE928FA4D, 0X2C030405, 0XB9325590, 0X20CB63BD, 0XA166305D,
        0X80E52C0A, 0XA8FAFE2F, 0X1AD13F7D, 0XCFAF3685, 0X6C83A199, 0X7D26718A, 0XDE5DFCD9, 0X79CF7355,
        0X8979D7FB, 0XEBF8C55E, 0XEBE408E4, 0XCD2AFFBA, 0XE483BE6E, 0XE239D6DE, 0X5DC1E9E0, 0X0473931F,
        0X851B097C, 0XAC5DB249, 0X09C0F9F2, 0XD8D2F134, 0XE6F38E41, 0XB1C71BF1, 0X52B6E4DB, 0X07224424,
        0X6CF73E85, 0X4F25D89C, 0X782A7D74, 0X10A68DCD, 0X3A868189, 0XD570D2DC, 0X69630745, 0X9542ED86,
        0X331CD6B2, 0XA84B5B28, 0X07879C9D, 0X38372F64, 0X7185DB11, 0X25BA7C83, 0X01061523, 0XE6792F9F,
        0XE5DF07D1, 0X4321B47F, 0X7D2469D8, 0X1A3A4F90, 0X48BE29A3, 0X669071AF, 0X8EC8DD31, 0X0810BFBF,
        0X813A06B4, 0X68538345, 0X65865DDC, 0X43A71B8E, 0X78619A56, 0X5A34451D, 0X5BDAA3ED, 0X71EDC7E9,
        0X17AC9A20, 0X78D10BFA, 0X6C1E7F35, 0XD51839D9, 0X240CBC51, 0X33513CC1, 0XD2B4F795, 0XCCAA8186,
        0X0BABE682, 0XA33CF164, 0X18C643EA, 0XC1CA105F, 0X9959147A, 0X6D3D94DE, 0X0B654FBE, 0XED902CA0,
        0X7D835CB5, 0X99BA1509, 0X6445C922, 0X495E76C2, 0XF07194BC, 0XA1631D7E, 0X677076A5, 0X89FFFE35,
        0X1A49BCF3, 0X8E6C948A, 0X0144C917, 0X8D93AEA1, 0X16F87DDF, 0XC8F25D49, 0X1FB11297, 0X27E750CD,
        0X2F422DA1, 0XDEE89A77, 0X1534C643, 0X457B7B8B, 0XAF172F7A, 0X6B9B09D6, 0X33573F7F, 0XF14E15C4,
        0X526467D5, 0XAF488241, 0X87C3EE0D, 0X33BE490C, 0X95AA6E52, 0X43EC242E, 0XD77DE99B, 0XD018334F,
        0X5B78D407, 0X498EB66B, 0XB1279FA8, 0XB38B0EA6, 0X90718376, 0XE325DEE2, 0X8E2F2CBA, 0XCAA5BDEC,
        0X9D652C56, 0XAD68F5CB, 0XA77591AF, 0X88E37EE8, 0XF8FAA221, 0XFCBBBE47, 0X4F407786, 0XAF393889,
        0XF444A1D9, 0X15AE1A2F, 0X40AA7097, 0X6F9486AC, 0X29D232A3, 0XE47609E9, 0XE8B631FF, 0XBA8565F4,
        0X11288749, 0X46C9A838, 0XEB1B7CD8, 0XF516BBB1, 0XFB74FDA0, 0X010996E6, 0X4C994653, 0X1D889512,
        0X53DCD9A3, 0XDD074697, 0X1E78E17C, 0X637C98BF, 0X930BB219, 0XCF7F75B0, 0XCB9355FB, 0X9E623009,
        0XE466D82C, 0X28F968D3, 0XFEB385D9, 0X238E026C, 0XB8ED0560, 0X0C6A027A, 0X3D6FEC4B, 0XBB4B2EC2,
        0XE715031C, 0XEDED011D, 0XCDC4D3B9, 0XC456FC96, 0XDD0EEA20, 0XB3DF8EC9, 0X12351993, 0XD9CBB01C,
        0X603147A2, 0XCF37D17D, 0XF7FCD9DC, 0XD8556FA3, 0X104C8131, 0X13152774, 0XB4715811, 0X6A72C2C9,
        0XC5AE37BB, 0XA76CE12A, 0X8150D8F3, 0X2EC29218, 0XA35F0984, 0X48C0647E, 0X0B5FF98C, 0X71893F7B
    };
    u32 mask = (1 << (msb64(avg) - 1)) - 1;

#define WINDOW_SIZE 2047
#define BARREL_SHIFT(v, shift) ( ((v) << (shift)) | ((v) >> ((32 - (shift)) & 0x1F)) )

    const u8 *d = data;
    u32 i, sum, imod;

    if (dlen <= min + WINDOW_SIZE) return dlen;

    sum = 0;
    for (i = WINDOW_SIZE - 1; i > 0; --i) {
        imod = i & 0x1F;
        sum ^= BARREL_SHIFT(T[*d], imod);
        ++d;
    }
    sum ^= T[*d];

    d = data;
    for (i = WINDOW_SIZE; i < dlen - WINDOW_SIZE; ++i) {
        sum = BARREL_SHIFT(sum, 1) ^ BARREL_SHIFT(T[*d], 0x1F) ^ T[d[WINDOW_SIZE]];
        if ((sum & mask) == 0) break;
        ++d;
    }
    if (i >= dlen - WINDOW_SIZE)
        i = dlen;

    return i;
}