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