Move some common input stuff around.
[fjl] / bitsource.h
1 #ifndef _BITSOURCE_H
2 #define _BITSOURCE_H 1
3
4 #include <assert.h>
5 #include <stddef.h>
6 #include <stdint.h>
7 #include <sys/types.h>
8 #include <arpa/inet.h>
9
10 #include "input.h"
11
12 // Optimize for 64 bits. We might want to replace this for 32-bit machines
13 // (benchmark later).
14 typedef uint64_t bitreservoir_t;
15 typedef uint32_t bitreservoir_fill_t;
16
17 static inline bitreservoir_fill_t read_bitreservoir_fill(uint8_t* source)
18 {
19         return ntohl(*(bitreservoir_fill_t*)(source));
20 }
21
22 static const unsigned BITRESERVOIR_SIZE = 8 * sizeof(bitreservoir_t);
23 static const unsigned BITRESERVOIR_FILL_SIZE = 8 * sizeof(bitreservoir_fill_t);
24 static const unsigned BYTERESERVOIR_SIZE = 4096;
25
26 // A data source for efficient reading of bit-level data.
27 struct bit_source {
28         // Short-term bit reservoir; holds up to 64 bits. When it's empty,
29         // it needs to get refilled from the medium-term bit reservoir.
30         bitreservoir_t bits;
31         unsigned bits_available;
32         
33         // Medium-term bit reservoir; holds a few kilobytes of spare data.
34         // When this is empty, it needs to be refilled from the input
35         // stream.
36         uint8_t* bytes;
37         unsigned bytes_available;
38
39         // Data source.
40         input_func_t* input_func;
41         void* userdata;
42 };
43
44 void init_bit_source(struct bit_source* source, input_func_t* input_func, void* userdata);
45
46 // Internal function. Do not use.
47 void possibly_refill_slow_path(struct bit_source* source, unsigned num_bits);
48
49 // Make sure there's at least NUM_BITS available in the short-term bit reservoir.
50 // You usually want to call this before read_bits(). The reason it's separate
51 // is that if you want two reads and you know the size of both, it's faster to
52 // refill A+B, read A, read B than refill A, read A, refill B, read B.
53 static inline void possibly_refill(struct bit_source* source, unsigned num_bits)
54 {
55         assert(num_bits <= BITRESERVOIR_FILL_SIZE + 1);
56
57         if (source->bits_available >= num_bits) {
58                 // Fast path (~90% of invocations?)
59                 return;
60         }
61
62         // Slower path (~99% of remaining invocations?)
63         assert(source->bits_available + BITRESERVOIR_FILL_SIZE < BITRESERVOIR_SIZE);
64         if (source->bytes_available >= sizeof(bitreservoir_fill_t)) {
65                 bitreservoir_fill_t fill = read_bitreservoir_fill(source->bytes);
66                 source->bytes += sizeof(bitreservoir_fill_t);
67                 source->bytes_available -= sizeof(bitreservoir_fill_t);
68                 source->bits |= (bitreservoir_t)fill << (BITRESERVOIR_SIZE - BITRESERVOIR_FILL_SIZE - source->bits_available);
69                 source->bits_available += BITRESERVOIR_FILL_SIZE;
70                 return;
71         }
72
73         // Slow path: Refill from data source.
74         // Should not be inlined, so split into a separate function.
75         possibly_refill_slow_path(source, num_bits);
76 }
77
78 static inline unsigned read_bits(struct bit_source* source, unsigned num_bits)
79 {
80         assert(source->bits_available >= num_bits);
81         unsigned ret = (source->bits >> (BITRESERVOIR_SIZE - num_bits));
82         source->bits <<= num_bits;
83         source->bits_available -= num_bits;
84         return ret;
85 }
86
87 static inline unsigned peek_bits(struct bit_source* source, unsigned num_bits)
88 {
89         assert(source->bits_available >= num_bits);
90         return (source->bits >> (BITRESERVOIR_SIZE - num_bits));
91 }
92
93 #endif /* !defined(_BITSOURCE_H) */