src/bitbuffer.c

   1 /**
   2  * Bit buffer
   3  *
   4  * A two-dimensional bit buffer consisting of bytes
   5  *
   6  * Copyright (C) 2015 Tommy Vestermark
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  */
  12
  13 #include "bitbuffer.h"
  14 #include <stdio.h>
  15 #include <string.h>
  16
  17
  18 void bitbuffer_clear(bitbuffer_t *bits) {
  19         bits->num_rows = 0;
  20         memset(bits->bits_per_row, 0, BITBUF_ROWS*2);
  21         memset(bits->bb, 0, BITBUF_ROWS * BITBUF_COLS);
  22 }
  23
  24
  25 void bitbuffer_add_bit(bitbuffer_t *bits, int bit) {
  26         if(bits->num_rows == 0) bits->num_rows++;       // Add first row automatically
  27         uint16_t col_index = bits->bits_per_row[bits->num_rows-1] / 8;
  28         uint16_t bit_index = bits->bits_per_row[bits->num_rows-1] % 8;
  29         if((col_index < BITBUF_COLS)
  30         && (bits->num_rows <= BITBUF_ROWS)
  31         ) {
  32                 bits->bb[bits->num_rows-1][col_index] |= (bit << (7-bit_index));
  33                 bits->bits_per_row[bits->num_rows-1]++;
  34         }
  35         else {
  36 //              fprintf(stderr, "ERROR: bitbuffer:: Could not add more columns\n");     // Some decoders may add many columns...
  37         }
  38 }
  39
  40
  41 void bitbuffer_add_row(bitbuffer_t *bits) {
  42         if(bits->num_rows == 0) bits->num_rows++;       // Add first row automatically
  43         if(bits->num_rows < BITBUF_ROWS) {
  44                 bits->num_rows++;
  45         }
  46         else {
  47 //              fprintf(stderr, "ERROR: bitbuffer:: Could not add more rows\n");        // Some decoders may add many rows...
  48         }
  49 }
  50
  51
  52 void bitbuffer_invert(bitbuffer_t *bits) {
  53         for (unsigned row = 0; row < bits->num_rows; ++row) {
  54                 if (bits->bits_per_row[row] > 0) {
  55                         const unsigned last_col  = (bits->bits_per_row[row]-1) / 8;
  56                         const unsigned last_bits = ((bits->bits_per_row[row]-1) % 8) +1;
  57                         for (unsigned col = 0; col <= last_col; ++col) {
  58                                 bits->bb[row][col] = ~bits->bb[row][col];       // Invert
  59                         }
  60                         bits->bb[row][last_col] ^= 0xFF >> last_bits;   // Re-invert unused bits in last byte
  61                 }
  62         }
  63 }
  64
  65
  66 void bitbuffer_extract_bytes(bitbuffer_t *bitbuffer, unsigned row,
  67                              unsigned pos, uint8_t *out, unsigned len)
  68 {
  69         uint8_t *bits = bitbuffer->bb[row];
  70
  71         if ((pos & 7) == 0) {
  72                 memcpy(out, bits + (pos / 8), (len + 7) / 8);
  73         } else {
  74                 unsigned shift = 8 - (pos & 7);
  75                 uint16_t word;
  76
  77                 pos >>= 3; // Convert to bytes
  78                 len >>= 3;
  79
  80                 word = bits[pos];
  81
  82                 while (len--) {
  83                         word <<= 8;
  84                         word |= bits[++pos];
  85                         *(out++) = word >> shift;
  86                 }
  87         }
  88 }
  89
  90 // If we make this an inline function instead of a macro, it means we don't
  91 // have to worry about using bit numbers with side-effects (bit++).
  92 static inline int bit(const uint8_t *bytes, unsigned bit)
  93 {
  94         return bytes[bit >> 3] >> (7 - (bit & 7)) & 1;
  95 }
  96
  97 unsigned bitbuffer_search(bitbuffer_t *bitbuffer, unsigned row, unsigned start,
  98                           const uint8_t *pattern, unsigned pattern_bits_len)
  99 {
 100     uint8_t *bits = bitbuffer->bb[row];
 101     unsigned len = bitbuffer->bits_per_row[row];
 102     unsigned ipos = start;
 103     unsigned ppos = 0;  // cursor on init pattern
 104
 105     while (ipos < len && ppos < pattern_bits_len) {
 106             if (bit(bits, ipos) == bit(pattern, ppos)) {
 107                     ppos++;
 108                     ipos++;
 109                     if (ppos == pattern_bits_len)
 110                             return ipos - pattern_bits_len;
 111             } else {
 112                     ipos += -ppos + 1;
 113                     ppos = 0;
 114             }
 115     }
 116
 117     // Not found
 118     return len;
 119 }
 120
 121 unsigned bitbuffer_manchester_decode(bitbuffer_t *inbuf, unsigned row, unsigned start,
 122                                      bitbuffer_t *outbuf, unsigned max)
 123 {
 124         uint8_t *bits = inbuf->bb[row];
 125         unsigned int len = inbuf->bits_per_row[row];
 126         unsigned int ipos = start;
 127
 128         if (max && len > start + (max * 2))
 129                 len = start + (max * 2);
 130
 131         while (ipos < len) {
 132                 uint8_t bit1, bit2;
 133
 134                 bit1 = bit(bits, ipos++);
 135                 bit2 = bit(bits, ipos++);
 136
 137                 if (bit1 == bit2)
 138                         break;
 139
 140                 bitbuffer_add_bit(outbuf, bit2);
 141         }
 142
 143         return ipos;
 144 }
 145
 146
 147 void bitbuffer_print(const bitbuffer_t *bits) {
 148         fprintf(stderr, "bitbuffer:: Number of rows: %d \n", bits->num_rows);
 149         for (uint16_t row = 0; row < bits->num_rows; ++row) {
 150                 fprintf(stderr, "[%02d] {%d} ", row, bits->bits_per_row[row]);
 151                 for (uint16_t col = 0; col < (bits->bits_per_row[row]+7)/8; ++col) {
 152                         fprintf(stderr, "%02x ", bits->bb[row][col]);
 153                 }
 154                 // Print binary values also?
 155                 if (bits->bits_per_row[row] <= BITBUF_MAX_PRINT_BITS) {
 156                         fprintf(stderr, ": ");
 157                         for (uint16_t bit = 0; bit < bits->bits_per_row[row]; ++bit) {
 158                                 if (bits->bb[row][bit/8] & (0x80 >> (bit % 8))) {
 159                                         fprintf(stderr, "1");
 160                                 } else {
 161                                         fprintf(stderr, "0");
 162                                 }
 163                                 if ((bit % 8) == 7) { fprintf(stderr, " "); }   // Add byte separators
 164                         }
 165                 }
 166                 fprintf(stderr, "\n");
 167         }
 168 }
 169
 170
 171 int compare_rows(bitbuffer_t *bits, unsigned row_a, unsigned row_b) {
 172         return (bits->bits_per_row[row_a] == bits->bits_per_row[row_b] &&
 173                 !memcmp(bits->bb[row_a], bits->bb[row_b],
 174                                 (bits->bits_per_row[row_a] + 7) / 8));
 175 }
 176
 177 unsigned count_repeats(bitbuffer_t *bits, unsigned row) {
 178         unsigned cnt = 0;
 179         for (int i = 0; i < bits->num_rows; ++i) {
 180                 if (compare_rows(bits, row, i)) {
 181                         ++cnt;
 182                 }
 183         }
 184         return cnt;
 185 }
 186
 187 int bitbuffer_find_repeated_row(bitbuffer_t *bits, unsigned min_repeats, unsigned min_bits) {
 188         for (int i = 0; i < bits->num_rows; ++i) {
 189                 if (bits->bits_per_row[i] >= min_bits &&
 190                         count_repeats(bits, i) >= min_repeats) {
 191                         return i;
 192                 }
 193         }
 194         return -1;
 195 }
 196
 197
 198 // Test code
 199 // gcc -I include/ -std=gnu11 -D _TEST src/bitbuffer.c
 200 #ifdef _TEST
 201 int main(int argc, char **argv) {
 202         fprintf(stderr, "bitbuffer:: test\n");
 203
 204         bitbuffer_t bits = {0};
 205
 206         fprintf(stderr, "TEST: bitbuffer:: The empty buffer\n");
 207         bitbuffer_print(&bits);
 208
 209         fprintf(stderr, "TEST: bitbuffer:: Add 1 bit\n");
 210         bitbuffer_add_bit(&bits, 1);
 211         bitbuffer_print(&bits);
 212
 213         fprintf(stderr, "TEST: bitbuffer:: Add 1 new row\n");
 214         bitbuffer_add_row(&bits);
 215         bitbuffer_print(&bits);
 216
 217         fprintf(stderr, "TEST: bitbuffer:: Fill row\n");
 218         for (int i=0; i < BITBUF_COLS*8; ++i) {
 219                 bitbuffer_add_bit(&bits, i%2);
 220         }
 221         bitbuffer_print(&bits);
 222
 223         fprintf(stderr, "TEST: bitbuffer:: Add row and fill 1 column too many\n");
 224         bitbuffer_add_row(&bits);
 225         for (int i=0; i <= BITBUF_COLS*8; ++i) {
 226                 bitbuffer_add_bit(&bits, i%2);
 227         }
 228         bitbuffer_print(&bits);
 229
 230         fprintf(stderr, "TEST: bitbuffer:: invert\n");
 231         bitbuffer_invert(&bits);
 232         bitbuffer_print(&bits);
 233
 234         fprintf(stderr, "TEST: bitbuffer:: Clear\n");
 235         bitbuffer_clear(&bits);
 236         bitbuffer_print(&bits);
 237
 238         fprintf(stderr, "TEST: bitbuffer:: Add 1 row too many\n");
 239         for (int i=0; i <= BITBUF_ROWS; ++i) {
 240                 bitbuffer_add_row(&bits);
 241         }
 242         bitbuffer_add_bit(&bits, 1);
 243         bitbuffer_print(&bits);
 244
 245         return 0;
 246 }
 247 #endif /* _TEST */