internet_checksum/

lib.rs

// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

//! RFC 1071 "internet checksum" computation.
//!
//! This crate implements the "internet checksum" defined in [RFC 1071] and
//! updated in [RFC 1141] and [RFC 1624], which is used by many different
//! protocols' packet formats. The checksum operates by computing the 1s
//! complement of the 1s complement sum of successive 16-bit words of the input.
//!
//! # Benchmarks
//!
//! ## [`Checksum::add_bytes`]
//!
//! The following microbenchmarks were performed on a 2018 Google Pixelbook. Each benchmark
//! constructs a [`Checksum`] object, calls [`Checksum::add_bytes`] with an input of the given
//! number of bytes, and then calls [`Checksum::checksum`] to finalize. Average values were
//! calculated over 3 trials.
//!
//! Bytes |    Time    |    Rate
//! ----- | ---------- | ----------
//!    20 |   2,649 ns |  7.55 MB/s
//!    31 |   3,826 ns |  8.10 MB/s
//!    32 |   3,871 ns |  8.27 MB/s
//!    64 |   1,433 ns |  44.7 MB/s
//!   128 |   2,225 ns |  57.5 MB/s
//!   256 |   3,829 ns |  66.9 MB/s
//!  1023 |  13,802 ns |  74.1 MB/s
//!  1024 |  13,535 ns |  75.7 MB/s
//!
//! ## [`Checksum::add_bytes_small`]
//!
//! The following microbenchmarks were performed on a 2018 Google Pixelbook. Each benchmark
//! constructs a [`Checksum`] object, calls [`Checksum::add_bytes_small`] with an input of the
//! given number of bytes, and then calls [`Checksum::checksum`] to finalize. Average values
//! were calculated over 3 trials.
//!
//! Bytes |    Time    |    Rate
//! ----- | ---------- | ----------
//!    20 |   2,639 ns |  7.57 MB/s
//!    31 |   3,806 ns |  8.15 MB/s
//!
//! ## [`update`]
//!
//! The following microbenchmarks were performed on a 2018 Google Pixelbook. Each benchmark
//! calls [`update`] with an original 2 byte checksum, and byteslices of specified lengths
//! to be updated. Average values were calculated over 3 trials.
//!
//! Bytes |    Time    |    Rate
//! ----- | ---------- | ----------
//!     2 |   1,550 ns |  1.29 MB/s
//!     4 |   1,972 ns |  2.03 MB/s
//!     8 |   2,892 ns |  2.77 MB/s
//!
//! [RFC 1071]: https://tools.ietf.org/html/rfc1071
//! [RFC 1141]: https://tools.ietf.org/html/rfc1141
//! [RFC 1624]: https://tools.ietf.org/html/rfc1624

// Optimizations applied:
//
// 0. Byteorder independence: as described in RFC 1071 section 2.(B)
//    The sum of 16-bit integers can be computed in either byte order,
//    so this actually saves us from the unnecessary byte swapping on
//    an LE machine. As perfed on a gLinux workstation, that swapping
//    can account for ~20% of the runtime.
//
// 1. Widen the accumulator: doing so enables us to process a bigger
//    chunk of data once at a time, achieving some kind of poor man's
//    SIMD. Currently a u128 counter is used on x86-64 and a u64 is
//    used conservatively on other architectures.
//
// 2. Process more at a time: the old implementation uses a u32 accumulator
//    but it only adds one u16 each time to implement deferred carry. In
//    the current implementation we are processing a u128 once at a time
//    on x86-64, which is 8 u16's. On other platforms, we are processing
//    a u64 at a time, which is 4 u16's.
//
// 3. Induce the compiler to produce `adc` instruction: this is a very
//    useful instruction to implement 1's complement addition and available
//    on both x86 and ARM. The functions `adc_uXX` are for this use.
//
// 4. Eliminate branching as much as possible: the old implementation has
//    if statements for detecting overflow of the u32 accumulator which
//    is not needed when we can access the carry flag with `adc`. The old
//    `normalize` function used to have a while loop to fold the u32,
//    however, we can unroll that loop because we know ahead of time how
//    much additions we need.
//
// 5. In the loop of `add_bytes`, the `adc_u64` is not used, instead,
//    the `overflowing_add` is directly used. `adc_u64`'s carry flag
//    comes from the current number being added while the slightly
//    convoluted version in `add_bytes`, adding each number depends on
//    the carry flag of the previous computation. I checked under release
//    mode this issues 3 instructions instead of 4 for x86 and it should
//    theoretically be beneficial, however, measurement showed me that it
//    helps only a little. So this trick is not used for `update`.
//
// 6. When the input is small, fallback to deferred carry method. Deferred
//    carry turns out to be very efficient when dealing with small buffers:
//    If the input is small, the cost to deal with the tail may already
//    outweigh the benefit of the unrolling itself. Some measurement
//    confirms this theory.
//
// Results:
//
// Micro-benchmarks are run on an x86-64 gLinux workstation. In summary,
// compared the baseline 0 which is prior to the byteorder independence
// patch, there is a ~4x speedup.
//
// TODO: run this optimization on other platforms. I would expect
// the situation on ARM a bit different because I am not sure
// how much penalty there will be for misaligned read on ARM, or
// whether it is even supported (On x86 there is generally no
// penalty for misaligned read). If there will be penalties, we
// should consider alignment as an optimization opportunity on ARM.

// TODO(joshlf): Right-justify the columns above

#![cfg_attr(feature = "benchmark", feature(test))]

#[cfg(all(test, feature = "benchmark"))]
extern crate test;

// TODO(joshlf):
// - Investigate optimizations proposed in RFC 1071 Section 2. The most
//   promising on modern hardware is probably (C) Parallel Summation, although
//   that needs to be balanced against (1) Deferred Carries. Benchmarks will
//   need to be performed to determine which is faster in practice, and under
//   what scenarios.

/// Compute the checksum of "bytes".
///
/// `checksum(bytes)` is shorthand for:
///
/// ```rust
/// # use internet_checksum::Checksum;
/// # let bytes = &[];
/// # let _ = {
/// let mut c = Checksum::new();
/// c.add_bytes(bytes);
/// c.checksum()
/// # };
/// ```
#[inline]
pub fn checksum(bytes: &[u8]) -> [u8; 2] {
    let mut c = Checksum::new();
    c.add_bytes(bytes);
    c.checksum()
}

#[cfg(target_arch = "x86_64")]
type Accumulator = u128;
#[cfg(not(target_arch = "x86_64"))]
type Accumulator = u64;

/// The threshold for small buffers, if the buffer is too small,
/// fall back to the normal deferred carry method where a wide
/// accumulator is used but one `u16` is added once at a time.
// TODO: `64` works fine on x86_64, but this value may be different
// on other platforms.
const SMALL_BUF_THRESHOLD: usize = 64;

/// The following macro unrolls operations on u16's to wider integers.
///
/// # Arguments
///
/// * `$arr`  - The byte slice being processed.
/// * `$body` - The operation to operate on the wider integer. It should
///             be a macro because functions are not options here.
///
///
/// This macro will choose the "wide integer" for you, on x86-64,
/// it will choose u128 as the "wide integer" and u64 anywhere else.
macro_rules! loop_unroll {
    (@inner $arr: ident, 16, $body:ident) => {
        while $arr.len() >= 16 {
            $body!(16, u128);
        }
        unroll_tail!($arr, 16, $body);
    };

    (@inner $arr: ident, 8, $body:ident) => {
        while $arr.len() >= 8 {
            $body!(8, u64);
        }
        unroll_tail!($arr, 8, $body);
    };

    ($arr: ident, $body: ident) => {
        #[cfg(target_arch = "x86_64")]
        loop_unroll!(@inner $arr, 16, $body);
        #[cfg(not(target_arch = "x86_64"))]
        loop_unroll!(@inner $arr, 8, $body);
    };
}

/// At the the end of loop unrolling, we have to take care of bytes
/// that are left over. For example, `unroll_tail!(bytes, 4, body)`
/// expands to
/// ```
/// if bytes.len & 2 != 0 {
///   body!(2, u16);
/// }
/// ```
macro_rules! unroll_tail {
    ($arr: ident, $n: literal, $read: ident, $body: ident) => {
        if $arr.len() & $n != 0 {
            $body!($n, $read);
        }
    };

    ($arr: ident, 4, $body: ident) => {
        unroll_tail!($arr, 2, u16, $body);
    };

    ($arr: ident, 8, $body: ident) => {
        unroll_tail!($arr, 4, u32, $body);
        unroll_tail!($arr, 4, $body);
    };

    ($arr: ident, 16, $body: ident) => {
        unroll_tail!($arr, 8, u64, $body);
        unroll_tail!($arr, 8, $body);
    };
}

/// Updates bytes in an existing checksum.
///
/// `update` updates a checksum to reflect that the already-checksummed bytes
/// `old` have been updated to contain the values in `new`. It implements the
/// algorithm described in Equation 3 in [RFC 1624]. The first byte must be at
/// an even number offset in the original input. If an odd number offset byte
/// needs to be updated, the caller should simply include the preceding byte as
/// well. If an odd number of bytes is given, it is assumed that these are the
/// last bytes of the input. If an odd number of bytes in the middle of the
/// input needs to be updated, the preceding or following byte of the input
/// should be added to make an even number of bytes.
///
/// # Panics
///
/// `update` panics if `old.len() != new.len()`.
///
/// [RFC 1624]: https://tools.ietf.org/html/rfc1624
#[inline]
pub fn update(checksum: [u8; 2], old: &[u8], new: &[u8]) -> [u8; 2] {
    assert_eq!(old.len(), new.len());
    // We compute on the sum, not the one's complement of the sum. checksum
    // is the one's complement of the sum, so we need to get back to the
    // sum. Thus, we negate checksum.
    // HC' = ~HC
    let mut sum = !u16::from_ne_bytes(checksum) as Accumulator;

    // Let's reuse `Checksum::add_bytes` to update our checksum
    // so that we can get the speedup for free. Using
    // [RFC 1071 Eqn. 3], we can efficiently update our new checksum.
    let mut c1 = Checksum::new();
    let mut c2 = Checksum::new();
    c1.add_bytes(old);
    c2.add_bytes(new);

    // Note, `c1.checksum_inner()` is actually ~m in [Eqn. 3]
    // `c2.checksum_inner()` is actually ~m' in [Eqn. 3]
    // so we have to negate `c2.checksum_inner()` first to get m'.
    // HC' += ~m, c1.checksum_inner() == ~m.
    sum = adc_accumulator(sum, c1.checksum_inner() as Accumulator);
    // HC' += m', c2.checksum_inner() == ~m'.
    sum = adc_accumulator(sum, !c2.checksum_inner() as Accumulator);
    // HC' = ~HC.
    (!normalize(sum)).to_ne_bytes()
}

/// RFC 1071 "internet checksum" computation.
///
/// `Checksum` implements the "internet checksum" defined in [RFC 1071] and
/// updated in [RFC 1141] and [RFC 1624], which is used by many different
/// protocols' packet formats. The checksum operates by computing the 1s
/// complement of the 1s complement sum of successive 16-bit words of the input.
///
/// [RFC 1071]: https://tools.ietf.org/html/rfc1071
/// [RFC 1141]: https://tools.ietf.org/html/rfc1141
/// [RFC 1624]: https://tools.ietf.org/html/rfc1624
#[derive(Default)]
pub struct Checksum {
    sum: Accumulator,
    // Since odd-length inputs are treated specially, we store the trailing byte
    // for use in future calls to add_bytes(), and only treat it as a true
    // trailing byte in checksum().
    trailing_byte: Option<u8>,
}

impl Checksum {
    /// Initialize a new checksum.
    #[inline]
    pub const fn new() -> Self {
        Checksum { sum: 0, trailing_byte: None }
    }

    /// Add bytes to the checksum.
    ///
    /// If `bytes` does not contain an even number of bytes, a single zero byte
    /// will be added to the end before updating the checksum.
    ///
    /// Note that `add_bytes` has some fixed overhead regardless of the size of
    /// `bytes`. Where performance is a concern, prefer fewer calls to
    /// `add_bytes` with larger input over more calls with smaller input.
    #[inline]
    pub fn add_bytes(&mut self, mut bytes: &[u8]) {
        use std::convert::TryInto;

        if bytes.len() < SMALL_BUF_THRESHOLD {
            self.add_bytes_small(bytes);
            return;
        }

        let mut sum = self.sum;
        let mut carry = false;

        // We are not using `adc_uXX` functions here, instead, we manually track
        // the carry flag. This is because in `adc_uXX` functions, the carry
        // flag depends on addition itself. So the assembly for that function
        // reads as follows:
        //
        // mov %rdi, %rcx
        // mov %rsi, %rax
        // add %rcx, %rsi -- waste! only used to generate CF.
        // adc %rdi, $rax -- the real useful instruction.
        //
        // So we had better to make us depend on the CF generated by the
        // addition of the previous 16-bit word. The ideal assembly should look
        // like:
        //
        // add 0(%rdi), %rax
        // adc 8(%rdi), %rax
        // adc 16(%rdi), %rax
        // .... and so on ...
        //
        // Sadly, there are too many instructions that can affect the carry
        // flag, and LLVM is not that optimized to find out the pattern and let
        // all these adc instructions not interleaved. However, doing so results
        // in 3 instructions instead of the original 4 instructions (the two
        // mov's are still there) and it makes a difference on input size like
        // 1023.

        // The following macro is used as a `body` when invoking a `loop_unroll`
        // macro. `$step` means how many bytes to handle at once; `$read` is
        // supposed to be `u16`, `u32` and so on, it is used to get an unsigned
        // integer of `$step` width from a byte slice; `$bytes` is the byte
        // slice mentioned before, if omitted, it defaults to be `bytes`, which
        // is the argument of the surrounding function.
        macro_rules! update_sum_carry {
            ($step: literal, $ty: ident, $bytes: expr) => {
                let (s, c) = sum
                    .overflowing_add($ty::from_ne_bytes($bytes.try_into().unwrap()) as Accumulator);
                sum = s + (carry as Accumulator);
                carry = c;
                bytes = &bytes[$step..];
            };
            ($step: literal, $ty: ident) => {
                update_sum_carry!($step, $ty, bytes[..$step]);
            };
        }

        // if there's a trailing byte, consume it first
        if let Some(byte) = self.trailing_byte {
            update_sum_carry!(1, u16, [byte, bytes[0]]);
            self.trailing_byte = None;
        }

        loop_unroll!(bytes, update_sum_carry);

        if bytes.len() == 1 {
            self.trailing_byte = Some(bytes[0]);
        }

        self.sum = sum + (carry as Accumulator);
    }

    /// The efficient fallback when the buffer is small.
    ///
    /// In this implementation, one `u16` is added once a
    /// time, so we don't waste time on dealing with the
    /// tail of the buffer. Besides, given that the accumulator
    /// is large enough, when inputs are small, there should
    /// hardly be overflows, so for any modern architecture,
    /// there is little chance in misprediction.
    // The inline attribute is needed here, micro benchmarks showed
    // that it speeds up things.
    #[inline(always)]
    fn add_bytes_small(&mut self, mut bytes: &[u8]) {
        if bytes.is_empty() {
            return;
        }

        let mut sum = self.sum;
        fn update_sum(acc: Accumulator, rhs: u16) -> Accumulator {
            if let Some(updated) = acc.checked_add(rhs as Accumulator) {
                updated
            } else {
                (normalize(acc) + rhs) as Accumulator
            }
        }

        if let Some(byte) = self.trailing_byte {
            sum = update_sum(sum, u16::from_ne_bytes([byte, bytes[0]]));
            bytes = &bytes[1..];
            self.trailing_byte = None;
        }

        bytes.chunks(2).for_each(|chunk| match chunk {
            [byte] => self.trailing_byte = Some(*byte),
            [first, second] => {
                sum = update_sum(sum, u16::from_ne_bytes([*first, *second]));
            }
            bytes => unreachable!("{:?}", bytes),
        });

        self.sum = sum;
    }

    /// Computes the checksum, but in big endian byte order.
    fn checksum_inner(&self) -> u16 {
        let mut sum = self.sum;
        if let Some(byte) = self.trailing_byte {
            sum = adc_accumulator(sum, u16::from_ne_bytes([byte, 0]) as Accumulator);
        }
        !normalize(sum)
    }

    /// Computes the checksum, and returns the array representation.
    ///
    /// `checksum` returns the checksum of all data added using `add_bytes` so
    /// far. Calling `checksum` does *not* reset the checksum. More bytes may be
    /// added after calling `checksum`, and they will be added to the checksum
    /// as expected.
    ///
    /// If an odd number of bytes have been added so far, the checksum will be
    /// computed as though a single 0 byte had been added at the end in order to
    /// even out the length of the input.
    #[inline]
    pub fn checksum(&self) -> [u8; 2] {
        self.checksum_inner().to_ne_bytes()
    }
}

macro_rules! impl_adc {
    ($name: ident, $t: ty) => {
        /// implements 1's complement addition for $t,
        /// exploiting the carry flag on a 2's complement machine.
        /// In practice, the adc instruction will be generated.
        fn $name(a: $t, b: $t) -> $t {
            let (s, c) = a.overflowing_add(b);
            s + (c as $t)
        }
    };
}

impl_adc!(adc_u16, u16);
impl_adc!(adc_u32, u32);
#[cfg(target_arch = "x86_64")]
impl_adc!(adc_u64, u64);
impl_adc!(adc_accumulator, Accumulator);

/// Normalizes the accumulator by mopping up the
/// overflow until it fits in a `u16`.
fn normalize(a: Accumulator) -> u16 {
    #[cfg(target_arch = "x86_64")]
    return normalize_64(adc_u64(a as u64, (a >> 64) as u64));
    #[cfg(not(target_arch = "x86_64"))]
    return normalize_64(a);
}

fn normalize_64(a: u64) -> u16 {
    let t = adc_u32(a as u32, (a >> 32) as u32);
    adc_u16(t as u16, (t >> 16) as u16)
}

#[cfg(all(test, feature = "benchmark"))]
mod benchmarks {
    extern crate test;
    use super::*;

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 31 bytes.
    #[bench]
    fn bench_checksum_31(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 31]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 32 bytes.
    #[bench]
    fn bench_checksum_32(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 32]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 64 bytes.
    #[bench]
    fn bench_checksum_64(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 64]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 128 bytes.
    #[bench]
    fn bench_checksum_128(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 128]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 256 bytes.
    #[bench]
    fn bench_checksum_256(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 256]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 1024 bytes.
    #[bench]
    fn bench_checksum_1024(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 1024]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    /// Benchmark time to calculate checksum with a single call to `add_bytes`
    /// with 1023 bytes.
    #[bench]
    fn bench_checksum_1023(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 1023]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    #[bench]
    fn bench_checksum_20(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 20]);
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            test::black_box(c.checksum());
        });
    }

    #[bench]
    fn bench_checksum_small_20(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 20]);
            let mut c = Checksum::new();
            c.add_bytes_small(&buf);
            test::black_box(c.checksum());
        });
    }

    #[bench]
    fn bench_checksum_small_31(b: &mut test::Bencher) {
        b.iter(|| {
            let buf = test::black_box([0xFF; 31]);
            let mut c = Checksum::new();
            c.add_bytes_small(&buf);
            test::black_box(c.checksum());
        });
    }

    #[bench]
    fn bench_update_2(b: &mut test::Bencher) {
        b.iter(|| {
            let old = test::black_box([0x42; 2]);
            let new = test::black_box([0xa0; 2]);
            test::black_box(update([42; 2], &old[..], &new[..]));
        });
    }

    #[bench]
    fn bench_update_4(b: &mut test::Bencher) {
        b.iter(|| {
            let old = test::black_box([0x42; 4]);
            let new = test::black_box([0xa0; 4]);
            test::black_box(update([42; 2], &old[..], &new[..]));
        });
    }

    #[bench]
    fn bench_update_8(b: &mut test::Bencher) {
        b.iter(|| {
            let old = test::black_box([0x42; 8]);
            let new = test::black_box([0xa0; 8]);
            test::black_box(update([42; 2], &old[..], &new[..]));
        });
    }
}

#[cfg(test)]
mod tests {
    use rand::{Rng, SeedableRng};

    use rand_xorshift::XorShiftRng;

    use super::*;

    /// Create a new deterministic RNG from a seed.
    fn new_rng(mut seed: u128) -> XorShiftRng {
        if seed == 0 {
            // XorShiftRng can't take 0 seeds
            seed = 1;
        }
        XorShiftRng::from_seed(seed.to_ne_bytes())
    }

    #[test]
    fn test_checksum() {
        for buf in IPV4_HEADERS {
            // compute the checksum as normal
            let mut c = Checksum::new();
            c.add_bytes(&buf);
            assert_eq!(c.checksum(), [0u8; 2]);
            // compute the checksum one byte at a time to make sure our
            // trailing_byte logic works
            let mut c = Checksum::new();
            for byte in *buf {
                c.add_bytes(&[*byte]);
            }
            assert_eq!(c.checksum(), [0u8; 2]);

            // Make sure that it works even if we overflow u32. Performing this
            // loop 2 * 2^16 times is guaranteed to cause such an overflow
            // because 0xFFFF + 0xFFFF > 2^16, and we're effectively adding
            // (0xFFFF + 0xFFFF) 2^16 times. We verify the overflow as well by
            // making sure that, at least once, the sum gets smaller from one
            // loop iteration to the next.
            let mut c = Checksum::new();
            c.add_bytes(&[0xFF, 0xFF]);
            for _ in 0..((2 * (1 << 16)) - 1) {
                c.add_bytes(&[0xFF, 0xFF]);
            }
            assert_eq!(c.checksum(), [0u8; 2]);
        }
    }

    #[test]
    fn test_update() {
        for b in IPV4_HEADERS {
            let mut buf = Vec::new();
            buf.extend_from_slice(b);

            let mut c = Checksum::new();
            c.add_bytes(&buf);
            assert_eq!(c.checksum(), [0u8; 2]);

            // replace the destination IP with the loopback address
            let old = [buf[16], buf[17], buf[18], buf[19]];
            (&mut buf[16..20]).copy_from_slice(&[127, 0, 0, 1]);
            let updated = update(c.checksum(), &old, &[127, 0, 0, 1]);
            let from_scratch = {
                let mut c = Checksum::new();
                c.add_bytes(&buf);
                c.checksum()
            };
            assert_eq!(updated, from_scratch);
        }
    }

    #[test]
    fn test_smoke_update() {
        let mut rng = new_rng(70_812_476_915_813);

        for _ in 0..2048 {
            // use an odd length so we test the odd length logic
            const BUF_LEN: usize = 31;
            let buf: [u8; BUF_LEN] = rng.gen();
            let mut c = Checksum::new();
            c.add_bytes(&buf);

            let (begin, end) = loop {
                let begin = rng.gen::<usize>() % BUF_LEN;
                let end = begin + (rng.gen::<usize>() % (BUF_LEN + 1 - begin));
                // update requires that begin is even and end is either even or
                // the end of the input
                if begin % 2 == 0 && (end % 2 == 0 || end == BUF_LEN) {
                    break (begin, end);
                }
            };

            let mut new_buf = buf;
            for i in begin..end {
                new_buf[i] = rng.gen();
            }
            let updated = update(c.checksum(), &buf[begin..end], &new_buf[begin..end]);
            let from_scratch = {
                let mut c = Checksum::new();
                c.add_bytes(&new_buf);
                c.checksum()
            };
            assert_eq!(updated, from_scratch);
        }
    }

    #[test]
    fn test_add_bytes_small_prop_test() {
        // Since we have two independent implementations
        // Now it is time for us to write a property test
        // to ensure the checksum algorithm(s) are indeed correct.

        let mut rng = new_rng(123478012483);
        let mut c1 = Checksum::new();
        let mut c2 = Checksum::new();
        for len in 64..1_025 {
            for _ in 0..4 {
                let mut buf = vec![];
                for _ in 0..len {
                    buf.push(rng.gen());
                }
                c1.add_bytes(&buf[..]);
                c2.add_bytes_small(&buf[..]);
                assert_eq!(c1.checksum(), c2.checksum());
                let n1 = c1.checksum_inner();
                let n2 = c2.checksum_inner();
                assert_eq!(n1, n2);
                let mut t1 = Checksum::new();
                let mut t2 = Checksum::new();
                let mut t3 = Checksum::new();
                t3.add_bytes(&buf[..]);
                if buf.len() % 2 == 1 {
                    buf.push(0);
                }
                assert_eq!(buf.len() % 2, 0);
                buf.extend_from_slice(&t3.checksum());
                t1.add_bytes(&buf[..]);
                t2.add_bytes_small(&buf[..]);
                assert_eq!(t1.checksum(), [0, 0]);
                assert_eq!(t2.checksum(), [0, 0]);
            }
        }
    }

    /// IPv4 headers.
    ///
    /// This data was obtained by capturing live network traffic.
    const IPV4_HEADERS: &[&[u8]] = &[
        &[
            0x45, 0x00, 0x00, 0x34, 0x00, 0x00, 0x40, 0x00, 0x40, 0x06, 0xae, 0xea, 0xc0, 0xa8,
            0x01, 0x0f, 0xc0, 0xb8, 0x09, 0x6a,
        ],
        &[
            0x45, 0x20, 0x00, 0x74, 0x5b, 0x6e, 0x40, 0x00, 0x37, 0x06, 0x5c, 0x1c, 0xc0, 0xb8,
            0x09, 0x6a, 0xc0, 0xa8, 0x01, 0x0f,
        ],
        &[
            0x45, 0x20, 0x02, 0x8f, 0x00, 0x00, 0x40, 0x00, 0x3b, 0x11, 0xc9, 0x3f, 0xac, 0xd9,
            0x05, 0x6e, 0xc0, 0xa8, 0x01, 0x0f,
        ],
    ];
}