29  * gives the number of set or unset bits.
35  * Still, there may be areas where the polarity flips every few bits,
44  * For some cases, we produce more code bits than plaintext input.
76  * Number of data bits follow fibonacci sequence, with the exception of the
78  * encoding bit polarity runlength is 1 plain bits => 2 code bits.
79 prefix    data bits                                    max val  Nº data bits
107  #................. s ...........................  plain bits  ..........
112 /* LEVEL: (total bits, prefix bits, prefix value),
113  * sorted ascending by number of total bits.
131  * returns number of bits consumed.
154 /* return number of code bits needed,
205 /* advance cursor by that many bits; maximum expected input value: 64,
207 static inline void bitstream_cursor_advance(struct bitstream_cursor *cur, unsigned int bits)  in bitstream_cursor_advance()  argument
209 	bits += cur->bit;  in bitstream_cursor_advance()
210 	cur->b = cur->b + (bits >> 3);  in bitstream_cursor_advance()
211 	cur->bit = bits & 7;  in bitstream_cursor_advance()
221 	 * number of trailing 0 bits for padding
222 	 * total number of valid bits in stream: buf_len * 8 - pad_bits */
240 /* Put (at most 64) least significant bits of val into bitstream, and advance cursor.
242  * Returns zero if bits == 0 (nothing to do).
243  * Returns number of bits used if successful.
248 static inline int bitstream_put_bits(struct bitstream *bs, u64 val, const unsigned int bits)  in bitstream_put_bits()  argument
253 	if (bits == 0)  in bitstream_put_bits()
256 	if ((bs->cur.b + ((bs->cur.bit + bits -1) >> 3)) - bs->buf >= bs->buf_len)  in bitstream_put_bits()
259 	/* paranoia: strip off hi bits; they should not be set anyways. */  in bitstream_put_bits()
260 	if (bits < 64)  in bitstream_put_bits()
261 		val &= ~0ULL >> (64 - bits);  in bitstream_put_bits()
265 	for (tmp = 8 - bs->cur.bit; tmp < bits; tmp += 8)  in bitstream_put_bits()
268 	bitstream_cursor_advance(&bs->cur, bits);  in bitstream_put_bits()
269 	return bits;  in bitstream_put_bits()
272 /* Fetch (at most 64) bits from bitstream into *out, and advance cursor.
274  * If more than 64 bits are requested, returns -EINVAL and leave *out unchanged.
276  * If there are less than the requested number of valid bits left in the
277  * bitstream, still fetches all available bits.
279  * Returns number of actually fetched bits.
281 static inline int bitstream_get_bits(struct bitstream *bs, u64 *out, int bits)  in bitstream_get_bits()  argument
286 	if (bits > 64)  in bitstream_get_bits()
289 	if (bs->cur.b + ((bs->cur.bit + bs->pad_bits + bits -1) >> 3) - bs->buf >= bs->buf_len)  in bitstream_get_bits()
290 		bits = ((bs->buf_len - (bs->cur.b - bs->buf)) << 3)  in bitstream_get_bits()
293 	if (bits == 0) {  in bitstream_get_bits()
298 	/* get the high bits */  in bitstream_get_bits()
300 	n = (bs->cur.bit + bits + 7) >> 3;  in bitstream_get_bits()
301 	/* n may be at most 9, if cur.bit + bits > 64 */  in bitstream_get_bits()
308 	/* we still need the low bits */  in bitstream_get_bits()
311 	/* and mask out bits we don't want */  in bitstream_get_bits()
312 	val &= ~0ULL >> (64 - bits);  in bitstream_get_bits()
314 	bitstream_cursor_advance(&bs->cur, bits);  in bitstream_get_bits()
317 	return bits;  in bitstream_get_bits()
323  *  > 0: number of bits successfully stored in bitstream
331 	int bits = __vli_encode_bits(&code, in);  in vli_encode_bits()  local
333 	if (bits <= 0)  in vli_encode_bits()
334 		return bits;  in vli_encode_bits()
336 	return bitstream_put_bits(bs, code, bits);  in vli_encode_bits()