^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: GPL-2.0-or-later */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) -*- linux-c -*-
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) drbd_receiver.c
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) This file is part of DRBD by Philipp Reisner and Lars Ellenberg.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) Copyright (C) 2001-2008, LINBIT Information Technologies GmbH.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) Copyright (C) 1999-2008, Philipp Reisner <philipp.reisner@linbit.com>.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) Copyright (C) 2002-2008, Lars Ellenberg <lars.ellenberg@linbit.com>.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #ifndef _DRBD_VLI_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #define _DRBD_VLI_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * At a granularity of 4KiB storage represented per bit,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * and stroage sizes of several TiB,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * and possibly small-bandwidth replication,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * the bitmap transfer time can take much too long,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * if transmitted in plain text.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * We try to reduce the transferred bitmap information
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * by encoding runlengths of bit polarity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * We never actually need to encode a "zero" (runlengths are positive).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * But then we have to store the value of the first bit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * The first bit of information thus shall encode if the first runlength
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) * gives the number of set or unset bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * We assume that large areas are either completely set or unset,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * which gives good compression with any runlength method,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * even when encoding the runlength as fixed size 32bit/64bit integers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * Still, there may be areas where the polarity flips every few bits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * and encoding the runlength sequence of those areas with fix size
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * integers would be much worse than plaintext.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) * We want to encode small runlength values with minimum code length,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * while still being able to encode a Huge run of all zeros.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * Thus we need a Variable Length Integer encoding, VLI.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * For some cases, we produce more code bits than plaintext input.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) * We need to send incompressible chunks as plaintext, skip over them
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * and then see if the next chunk compresses better.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * We don't care too much about "excellent" compression ratio for large
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * runlengths (all set/all clear): whether we achieve a factor of 100
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * or 1000 is not that much of an issue.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * We do not want to waste too much on short runlengths in the "noisy"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * parts of the bitmap, though.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * There are endless variants of VLI, we experimented with:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * * simple byte-based
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * * various bit based with different code word length.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * To avoid yet an other configuration parameter (choice of bitmap compression
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * algorithm) which was difficult to explain and tune, we just chose the one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * variant that turned out best in all test cases.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * Based on real world usage patterns, with device sizes ranging from a few GiB
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * to several TiB, file server/mailserver/webserver/mysql/postgress,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * mostly idle to really busy, the all time winner (though sometimes only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * marginally better) is:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * encoding is "visualised" as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * __little endian__ bitstream, least significant bit first (left most)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) * this particular encoding is chosen so that the prefix code
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * starts as unary encoding the level, then modified so that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * 10 levels can be described in 8bit, with minimal overhead
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * for the smaller levels.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) * Number of data bits follow fibonacci sequence, with the exception of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * last level (+1 data bit, so it makes 64bit total). The only worse code when
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) * encoding bit polarity runlength is 1 plain bits => 2 code bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) prefix data bits max val Nº data bits
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) 0 x 0x2 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) 10 x 0x4 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) 110 xx 0x8 2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) 1110 xxx 0x10 3
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) 11110 xxx xx 0x30 5
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) 111110 xx xxxxxx 0x130 8
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) 11111100 xxxxxxxx xxxxx 0x2130 13
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) 11111110 xxxxxxxx xxxxxxxx xxxxx 0x202130 21
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) 11111101 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xx 0x400202130 34
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) 11111111 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 56
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * maximum encodable value: 0x100000400202130 == 2**56 + some */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) /* compression "table":
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) transmitted x 0.29
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) as plaintext x ........................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) x ........................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) x ........................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) x 0.59 0.21........................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) x ........................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) x .. c ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) x 0.44.. o ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) x .......... d ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) x .......... e ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) X............. ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) x.............. b ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) 2.0x............... i ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) #X................ t ...................................................
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) #................. s ........................... plain bits ..........
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) -+-----------------------------------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) 1 16 32 64
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) /* LEVEL: (total bits, prefix bits, prefix value),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) * sorted ascending by number of total bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) * The rest of the code table is calculated at compiletime from this. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) /* fibonacci data 1, 1, ... */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) #define VLI_L_1_1() do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) LEVEL( 2, 1, 0x00); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) LEVEL( 3, 2, 0x01); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) LEVEL( 5, 3, 0x03); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) LEVEL( 7, 4, 0x07); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) LEVEL(10, 5, 0x0f); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) LEVEL(14, 6, 0x1f); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) LEVEL(21, 8, 0x3f); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) LEVEL(29, 8, 0x7f); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) LEVEL(42, 8, 0xbf); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) LEVEL(64, 8, 0xff); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) /* finds a suitable level to decode the least significant part of in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) * returns number of bits consumed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) * BUG() for bad input, as that would mean a buggy code table. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) static inline int vli_decode_bits(u64 *out, const u64 in)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) u64 adj = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) #define LEVEL(t,b,v) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) if ((in & ((1 << b) -1)) == v) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) *out = ((in & ((~0ULL) >> (64-t))) >> b) + adj; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) return t; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) adj += 1ULL << (t - b); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) VLI_L_1_1();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) /* NOT REACHED, if VLI_LEVELS code table is defined properly */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) BUG();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) #undef LEVEL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) /* return number of code bits needed,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) * or negative error number */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) static inline int __vli_encode_bits(u64 *out, const u64 in)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) u64 max = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) u64 adj = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) if (in == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) #define LEVEL(t,b,v) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) max += 1ULL << (t - b); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) if (in <= max) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) if (out) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) *out = ((in - adj) << b) | v; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) return t; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) adj = max + 1; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) VLI_L_1_1();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) return -EOVERFLOW;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) #undef LEVEL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) #undef VLI_L_1_1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) /* code from here down is independend of actually used bit code */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) * Code length is determined by some unique (e.g. unary) prefix.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) * This encodes arbitrary bit length, not whole bytes: we have a bit-stream,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) * not a byte stream.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) /* for the bitstream, we need a cursor */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) struct bitstream_cursor {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) /* the current byte */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) u8 *b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) /* the current bit within *b, nomalized: 0..7 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) unsigned int bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) /* initialize cursor to point to first bit of stream */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) static inline void bitstream_cursor_reset(struct bitstream_cursor *cur, void *s)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) cur->b = s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) cur->bit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) /* advance cursor by that many bits; maximum expected input value: 64,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) * but depending on VLI implementation, it may be more. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) static inline void bitstream_cursor_advance(struct bitstream_cursor *cur, unsigned int bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) bits += cur->bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) cur->b = cur->b + (bits >> 3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) cur->bit = bits & 7;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) /* the bitstream itself knows its length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) struct bitstream {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) struct bitstream_cursor cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) unsigned char *buf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) size_t buf_len; /* in bytes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) /* for input stream:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) * number of trailing 0 bits for padding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) * total number of valid bits in stream: buf_len * 8 - pad_bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) unsigned int pad_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) static inline void bitstream_init(struct bitstream *bs, void *s, size_t len, unsigned int pad_bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) bs->buf = s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) bs->buf_len = len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) bs->pad_bits = pad_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) bitstream_cursor_reset(&bs->cur, bs->buf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) static inline void bitstream_rewind(struct bitstream *bs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) bitstream_cursor_reset(&bs->cur, bs->buf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) memset(bs->buf, 0, bs->buf_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) /* Put (at most 64) least significant bits of val into bitstream, and advance cursor.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) * Ignores "pad_bits".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) * Returns zero if bits == 0 (nothing to do).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) * Returns number of bits used if successful.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) * If there is not enough room left in bitstream,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) * leaves bitstream unchanged and returns -ENOBUFS.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) static inline int bitstream_put_bits(struct bitstream *bs, u64 val, const unsigned int bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) unsigned char *b = bs->cur.b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) unsigned int tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) if (bits == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) if ((bs->cur.b + ((bs->cur.bit + bits -1) >> 3)) - bs->buf >= bs->buf_len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) return -ENOBUFS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) /* paranoia: strip off hi bits; they should not be set anyways. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) if (bits < 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) val &= ~0ULL >> (64 - bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) *b++ |= (val & 0xff) << bs->cur.bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) for (tmp = 8 - bs->cur.bit; tmp < bits; tmp += 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) *b++ |= (val >> tmp) & 0xff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) bitstream_cursor_advance(&bs->cur, bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) return bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) /* Fetch (at most 64) bits from bitstream into *out, and advance cursor.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) * If more than 64 bits are requested, returns -EINVAL and leave *out unchanged.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) * If there are less than the requested number of valid bits left in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) * bitstream, still fetches all available bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) * Returns number of actually fetched bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) static inline int bitstream_get_bits(struct bitstream *bs, u64 *out, int bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) u64 val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) unsigned int n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) if (bits > 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) if (bs->cur.b + ((bs->cur.bit + bs->pad_bits + bits -1) >> 3) - bs->buf >= bs->buf_len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) bits = ((bs->buf_len - (bs->cur.b - bs->buf)) << 3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) - bs->cur.bit - bs->pad_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) if (bits == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) *out = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) /* get the high bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) val = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) n = (bs->cur.bit + bits + 7) >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) /* n may be at most 9, if cur.bit + bits > 64 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) /* which means this copies at most 8 byte */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) if (n) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) memcpy(&val, bs->cur.b+1, n - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) val = le64_to_cpu(val) << (8 - bs->cur.bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) /* we still need the low bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) val |= bs->cur.b[0] >> bs->cur.bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) /* and mask out bits we don't want */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) val &= ~0ULL >> (64 - bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) bitstream_cursor_advance(&bs->cur, bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) *out = val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) return bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) /* encodes @in as vli into @bs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) * return values
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) * > 0: number of bits successfully stored in bitstream
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) * -ENOBUFS @bs is full
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) * -EINVAL input zero (invalid)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) * -EOVERFLOW input too large for this vli code (invalid)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) static inline int vli_encode_bits(struct bitstream *bs, u64 in)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) u64 code = code;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) int bits = __vli_encode_bits(&code, in);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) if (bits <= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) return bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) return bitstream_put_bits(bs, code, bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) #endif
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags