git.sesse.net Git - fjl/blob - 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 static inline unsigned peek_bits(struct bit_source* source, unsigned num_bits)
  91 {
  92         assert(source->bits_available >= num_bits);
  93         return (source->bits >> (BITRESERVOIR_SIZE - num_bits));
  94 }
  95
  96 #endif /* !defined(_INPUT_H) */