anvil_db 0.2.2

an embedded key-value store
Documentation 
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/// See [1] for the spec that this is based on.
/// 1. https://datatracker.ietf.org/doc/html/rfc1952#section-8
pub(crate) fn crc32(prev: u32, buf: &[u8]) -> u32 {
    // Ideally, the following CRC table would be generated by a macro.
    // However, using a procedural macro would require introducing another
    // crate, which seems like overkill for this use case. For future
    // reference, the CRC table could be generated at run time with the
    // following code.

    // let mut table = vec![0_u32; 256];
    // for (n, table_cell) in table.iter_mut().enumerate() {
    //     let mut c = n as u32;
    //     for _ in 0..8 {
    //         if c & 1 == 1 {
    //             c = 0xedb88320 ^ (c >> 1);
    //         } else {
    //             c >>= 1;
    //         }
    //     }
    //     *table_cell = c;
    // }

    let table = [
        0, 1996959894, 3993919788, 2567524794, 124634137, 1886057615, 3915621685, 2657392035,
        249268274, 2044508324, 3772115230, 2547177864, 162941995, 2125561021, 3887607047,
        2428444049, 498536548, 1789927666, 4089016648, 2227061214, 450548861, 1843258603,
        4107580753, 2211677639, 325883990, 1684777152, 4251122042, 2321926636, 335633487,
        1661365465, 4195302755, 2366115317, 997073096, 1281953886, 3579855332, 2724688242,
        1006888145, 1258607687, 3524101629, 2768942443, 901097722, 1119000684, 3686517206,
        2898065728, 853044451, 1172266101, 3705015759, 2882616665, 651767980, 1373503546,
        3369554304, 3218104598, 565507253, 1454621731, 3485111705, 3099436303, 671266974,
        1594198024, 3322730930, 2970347812, 795835527, 1483230225, 3244367275, 3060149565,
        1994146192, 31158534, 2563907772, 4023717930, 1907459465, 112637215, 2680153253,
        3904427059, 2013776290, 251722036, 2517215374, 3775830040, 2137656763, 141376813,
        2439277719, 3865271297, 1802195444, 476864866, 2238001368, 4066508878, 1812370925,
        453092731, 2181625025, 4111451223, 1706088902, 314042704, 2344532202, 4240017532,
        1658658271, 366619977, 2362670323, 4224994405, 1303535960, 984961486, 2747007092,
        3569037538, 1256170817, 1037604311, 2765210733, 3554079995, 1131014506, 879679996,
        2909243462, 3663771856, 1141124467, 855842277, 2852801631, 3708648649, 1342533948,
        654459306, 3188396048, 3373015174, 1466479909, 544179635, 3110523913, 3462522015,
        1591671054, 702138776, 2966460450, 3352799412, 1504918807, 783551873, 3082640443,
        3233442989, 3988292384, 2596254646, 62317068, 1957810842, 3939845945, 2647816111, 81470997,
        1943803523, 3814918930, 2489596804, 225274430, 2053790376, 3826175755, 2466906013,
        167816743, 2097651377, 4027552580, 2265490386, 503444072, 1762050814, 4150417245,
        2154129355, 426522225, 1852507879, 4275313526, 2312317920, 282753626, 1742555852,
        4189708143, 2394877945, 397917763, 1622183637, 3604390888, 2714866558, 953729732,
        1340076626, 3518719985, 2797360999, 1068828381, 1219638859, 3624741850, 2936675148,
        906185462, 1090812512, 3747672003, 2825379669, 829329135, 1181335161, 3412177804,
        3160834842, 628085408, 1382605366, 3423369109, 3138078467, 570562233, 1426400815,
        3317316542, 2998733608, 733239954, 1555261956, 3268935591, 3050360625, 752459403,
        1541320221, 2607071920, 3965973030, 1969922972, 40735498, 2617837225, 3943577151,
        1913087877, 83908371, 2512341634, 3803740692, 2075208622, 213261112, 2463272603,
        3855990285, 2094854071, 198958881, 2262029012, 4057260610, 1759359992, 534414190,
        2176718541, 4139329115, 1873836001, 414664567, 2282248934, 4279200368, 1711684554,
        285281116, 2405801727, 4167216745, 1634467795, 376229701, 2685067896, 3608007406,
        1308918612, 956543938, 2808555105, 3495958263, 1231636301, 1047427035, 2932959818,
        3654703836, 1088359270, 936918000, 2847714899, 3736837829, 1202900863, 817233897,
        3183342108, 3401237130, 1404277552, 615818150, 3134207493, 3453421203, 1423857449,
        601450431, 3009837614, 3294710456, 1567103746, 711928724, 3020668471, 3272380065,
        1510334235, 755167117,
    ];

    // compute the CRC hash
    let mut c = prev ^ 0xffffffff;
    for byte in buf {
        let idx = ((c ^ (*byte as u32)) & 0xff) as usize;
        c = table[idx] ^ (c >> 8);
    }
    c ^ 0xffffffff
}

#[cfg(test)]
mod tests {
    use super::*;

    extern crate test;
    use test::Bencher;

    #[test]
    fn test_empty_buffer() {
        let data = b"";
        let checksum = crc32(0, data);
        assert_eq!(checksum, 0x0);
    }

    #[test]
    fn test_crc32() {
        let test_vectors = [
            ("123456789", 0xCBF43926),
            ("The quick brown fox jumps over the lazy dog", 0x414FA339),
        ];

        for (data, expected_crc) in test_vectors {
            let actual_crc = crc32(0, data.as_bytes());
            assert_eq!(actual_crc, expected_crc);
        }
    }

    #[test]
    fn test_single_byte_buffer() {
        let data = b"a";
        let checksum = crc32(0, data);

        let expect = 3904355907;
        assert_eq!(
            checksum, expect,
            "expected {expect:#02X} but got {checksum:#02X}",
        );
    }

    #[test]
    fn test_hello_world_checksum() {
        let data = b"Hello, World!";
        let checksum = crc32(0, data);
        assert_eq!(checksum, 3964322768);
    }

    #[bench]
    fn bench_crc32(b: &mut Bencher) {
        let data: Vec<_> = (0..128).collect();
        b.iter(|| crc32(0, &data));
    }
}