Welcome to little lamb

Code » test-rolling-hash » next » tree

[next] / src / rabin-mix.c 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <string.h> /* size_t */
#include <limb/int.h>
#include "rabin-tables.h"

size_t
nextsplit(size_t min, size_t avg, const void *data, size_t dlen)
{
    if (dlen <= min) return dlen;
    u8 window[RABIN_WINDOW_SIZE] = { 0 };
    const u8 *b = data;
    size_t wpos = 0, pos = min, last = 0;
    u64 fp = 0;
    u64 mask, lrg_mask;
    int tttd = avg >= (128 << 10);
    if (tttd)
        mask = (1 << (msb64(avg    ) - 1)) - 1;
    else
        mask = (1 << (msb64(avg * 2) - 1)) - 1;
    lrg_mask = (1 << (msb64(avg / 2) - 1)) - 1;

#define TTTD_BREAK      0x78
#define APPEND8(p,m)    (((p) << 8) | m) ^ rabin_tables.T[(p) >> 55]
    for (;;) {
        u8 old = window[wpos];
        window[wpos] = b[pos];
        fp = APPEND8(fp ^ rabin_tables.U[old], window[wpos]);
        if (++wpos == sizeof(window)) wpos = 0;

        if (pos == dlen) {
            if (last) return last;
            return pos;
        }
        if (pos >= min) {
            if (tttd) {
                if ((fp & lrg_mask) == TTTD_BREAK) {
                    if ((fp & mask) == TTTD_BREAK)
                        return pos;
                    last = pos;
                }
            } else if (pos < avg) {
                if ((fp & mask) == mask)
                    return pos;
            } else if ((fp & lrg_mask) == lrg_mask) {
                return pos;
            }
        }
        ++pos;
    }
}