| 1 |
|
| /* po_bits.h - a bit writer and a bit reader. |
| 2 |
|
| * |
| 3 |
|
| * Everything in phase 5 sits on these two, so they are deliberately small and |
| 4 |
|
| * exhaustively tested. A bug here is not a crash, it is a chart with a spike |
| 5 |
|
| * in the wrong place. |
| 6 |
|
| * |
| 7 |
|
| * Bits are written most-significant-first within each byte, which is the |
| 8 |
|
| * convention the Gorilla paper's control codes assume ('10', '110', '1110') |
| 9 |
|
| * and the one that makes a hex dump readable when something is wrong. |
| 10 |
|
| */ |
| 11 |
|
| #ifndef PO_BITS_H |
| 12 |
|
| #define PO_BITS_H |
| 13 |
|
| |
| 14 |
|
| #include "punk_observe/po_compat.h" |
| 15 |
|
| |
| 16 |
|
| typedef struct { |
| 17 |
|
| unsigned char *buf; |
| 18 |
|
| size_t cap; /* bytes */ |
| 19 |
|
| size_t nbits; |
| 20 |
|
| int err; /* set on allocation failure; sticky */ |
| 21 |
|
| } po_bw; |
| 22 |
|
| |
| 23 |
115 |
| static int po_bw_init(po_bw *w, size_t hint) { |
| 24 |
115 |
| memset(w, 0, sizeof(*w)); |
| 25 |
115 |
▶ | w->cap = hint ? hint : 64; |
Branch: 1 branch
| Branch | True | False | Total |
| w->cap = hint ? hint : 64; |
115 |
0 |
115 |
|
| 26 |
115 |
| w->buf = (unsigned char *)calloc(w->cap, 1); |
| 27 |
115 |
| return w->buf != NULL; |
| 28 |
|
| } |
| 29 |
|
| |
| 30 |
115 |
| static void po_bw_free(po_bw *w) { free(w->buf); w->buf = NULL; w->cap = 0; } |
| 31 |
|
| |
| 32 |
420375 |
| static int po_bw_room(po_bw *w, size_t more_bits) { |
| 33 |
420375 |
| size_t need = (w->nbits + more_bits + 7) / 8; |
| 34 |
420375 |
▶ | if (need <= w->cap) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (need <= w->cap) return 1; |
420338 |
37 |
420375 |
|
| 35 |
|
| { |
| 36 |
37 |
| size_t want = w->cap * 2; |
| 37 |
|
| unsigned char *nb; |
| 38 |
37 |
▶ | while (want < need) want *= 2; |
Branch: 1 branch
| Branch | True | False | Total |
| while (want < need) want *= 2; |
0 |
37 |
37 |
|
| 39 |
37 |
| nb = (unsigned char *)realloc(w->buf, want); |
| 40 |
37 |
▶ | if (!nb) { w->err = 1; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!nb) { w->err = 1; return 0; } |
0 |
37 |
37 |
|
| 41 |
37 |
| memset(nb + w->cap, 0, want - w->cap); /* new bytes must be zero */ |
| 42 |
37 |
| w->buf = nb; |
| 43 |
37 |
| w->cap = want; |
| 44 |
|
| } |
| 45 |
37 |
| return 1; |
| 46 |
|
| } |
| 47 |
|
| |
| 48 |
|
| /* Write the low `n` bits of `v`, most significant of those first. */ |
| 49 |
420375 |
| static void po_bw_put(po_bw *w, po_u64 v, int n) { |
| 50 |
|
| int i; |
| 51 |
420375 |
▶ | if (w->err || n <= 0) return; |
Branch: 2 branches
| Branch | True | False | Total |
| if (w->err || n <= 0) return; |
420375 |
0 |
420375 |
| if (w->err || n <= 0) return; |
0 |
420375 |
420375 |
|
| 52 |
420375 |
▶ | if (!po_bw_room(w, (size_t)n)) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_bw_room(w, (size_t)n)) return; |
0 |
420375 |
420375 |
|
| 53 |
7242749 |
▶ | for (i = n - 1; i >= 0; i--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = n - 1; i >= 0; i--) { |
6822374 |
420375 |
7242749 |
|
| 54 |
6822374 |
| size_t bit = w->nbits; |
| 55 |
6822374 |
| size_t byte = bit >> 3; |
| 56 |
6822374 |
| int off = 7 - (int)(bit & 7); |
| 57 |
6822374 |
▶ | if ((v >> i) & 1) w->buf[byte] |= (unsigned char)(1 << off); |
Branch: 1 branch
| Branch | True | False | Total |
| if ((v >> i) & 1) w->buf[byte] |= (unsigned char)(1 << off); |
3219363 |
3603011 |
6822374 |
|
| 58 |
6822374 |
| w->nbits++; |
| 59 |
|
| } |
| 60 |
|
| } |
| 61 |
|
| |
| 62 |
314543 |
| static void po_bw_put1(po_bw *w, int b) { po_bw_put(w, b ? 1 : 0, 1); } |
| 63 |
|
| |
| 64 |
45 |
| static size_t po_bw_bytes(const po_bw *w) { return (w->nbits + 7) / 8; } |
| 65 |
|
| |
| 66 |
|
| typedef struct { |
| 67 |
|
| const unsigned char *buf; |
| 68 |
|
| size_t nbits; /* total available */ |
| 69 |
|
| size_t pos; |
| 70 |
|
| int err; /* set on a read past the end */ |
| 71 |
|
| } po_br; |
| 72 |
|
| |
| 73 |
113 |
| static void po_br_init(po_br *r, const void *buf, size_t nbits) { |
| 74 |
113 |
| r->buf = (const unsigned char *)buf; |
| 75 |
113 |
| r->nbits = nbits; |
| 76 |
113 |
| r->pos = 0; |
| 77 |
113 |
| r->err = 0; |
| 78 |
113 |
| } |
| 79 |
|
| |
| 80 |
|
| /* Read `n` bits. On a read past the end this sets err and returns 0 rather |
| 81 |
|
| * than reading whatever follows the buffer - a truncated chunk must fail, not |
| 82 |
|
| * decode to plausible garbage. */ |
| 83 |
420327 |
| static po_u64 po_br_get(po_br *r, int n) { |
| 84 |
420327 |
| po_u64 v = 0; |
| 85 |
|
| int i; |
| 86 |
420327 |
▶ | if (r->err || n <= 0) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (r->err || n <= 0) return 0; |
420327 |
0 |
420327 |
| if (r->err || n <= 0) return 0; |
0 |
420327 |
420327 |
|
| 87 |
420327 |
▶ | if (r->pos + (size_t)n > r->nbits) { r->err = 1; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->pos + (size_t)n > r->nbits) { r->err = 1; return 0; } |
0 |
420327 |
420327 |
|
| 88 |
7242076 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
6821749 |
420327 |
7242076 |
|
| 89 |
6821749 |
| size_t bit = r->pos; |
| 90 |
6821749 |
| size_t byte = bit >> 3; |
| 91 |
6821749 |
| int off = 7 - (int)(bit & 7); |
| 92 |
6821749 |
| v = (v << 1) | (po_u64)((r->buf[byte] >> off) & 1); |
| 93 |
6821749 |
| r->pos++; |
| 94 |
|
| } |
| 95 |
420327 |
| return v; |
| 96 |
|
| } |
| 97 |
|
| |
| 98 |
314552 |
| static int po_br_get1(po_br *r) { return (int)po_br_get(r, 1); } |
| 99 |
|
| |
| 100 |
|
| /* Sign-extend an n-bit two's-complement value. |
| 101 |
|
| * |
| 102 |
|
| * This is where bit-stream code goes wrong, and the symptom is not a crash: |
| 103 |
|
| * a 12-bit delta-of-delta of -2047 read back as 2049 puts a point in the |
| 104 |
|
| * wrong place on a chart and nothing anywhere reports a problem. */ |
| 105 |
28 |
| static po_i64 po_sext(po_u64 v, int n) { |
| 106 |
28 |
| po_u64 m = (po_u64)1 << (n - 1); |
| 107 |
28 |
▶ | if (v & m) return (po_i64)(v | ~(((po_u64)1 << n) - 1)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (v & m) return (po_i64)(v | ~(((po_u64)1 << n) - 1)); |
16 |
12 |
28 |
|
| 108 |
12 |
| return (po_i64)v; |
| 109 |
|
| } |
| 110 |
|
| |
| 111 |
|
| #endif /* PO_BITS_H */ |