include/bitbuffer.h

   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 #ifndef INCLUDE_BITBUFFER_H_
  14 #define INCLUDE_BITBUFFER_H_
  15
  16 #include <stdint.h>
  17
  18 #define BITBUF_COLS             80              // Number of bytes in a column
  19 #define BITBUF_ROWS             25
  20 #define BITBUF_MAX_PRINT_BITS   50      // Maximum number of bits to print (in addition to hex values)
  21
  22 typedef uint8_t bitrow_t[BITBUF_COLS];
  23 typedef bitrow_t bitarray_t[BITBUF_ROWS];
  24
  25 /// Bit buffer
  26 typedef struct {
  27         uint16_t        num_rows;       // Number of active rows
  28         uint16_t        bits_per_row[BITBUF_ROWS];      // Number of active bits per row
  29         bitarray_t      bb;                     // The actual bits buffer
  30 } bitbuffer_t;
  31
  32
  33 /// Clear the content of the bitbuffer
  34 void bitbuffer_clear(bitbuffer_t *bits);
  35
  36 /// Add a single bit at the end of the bitbuffer (MSB first)
  37 void bitbuffer_add_bit(bitbuffer_t *bits, int bit);
  38
  39 /// Add a new row to the bitbuffer
  40 void bitbuffer_add_row(bitbuffer_t *bits);
  41
  42 /// Extract (potentially unaligned) bytes from the bit buffer. Len is bits.
  43 void bitbuffer_extract_bytes(bitbuffer_t *bitbuffer, unsigned row,
  44                              unsigned pos, uint8_t *out, unsigned len);
  45
  46 /// Invert all bits in the bitbuffer (do not invert the empty bits)
  47 void bitbuffer_invert(bitbuffer_t *bits);
  48
  49 /// Print the content of the bitbuffer
  50 void bitbuffer_print(const bitbuffer_t *bits);
  51
  52 // Search the specified row of the bitbuffer, starting from bit 'start', for
  53 // the pattern provided. Return the location of the first match, or the end
  54 // of the row if no match is found.
  55 // The pattern starts in the high bit. For example if searching for 011011
  56 // the byte pointed to by 'pattern' would be 0xAC. (011011xx).
  57 unsigned bitbuffer_search(bitbuffer_t *bitbuffer, unsigned row, unsigned start,
  58                           const uint8_t *pattern, unsigned pattern_bits_len);
  59
  60 // Manchester decoding from one bitbuffer into another, starting at the
  61 // specified row and start bit. Decode at most 'max' data bits (i.e. 2*max)
  62 // bits from the input buffer). Return the bit position in the input row
  63 // (i.e. returns start + 2*outbuf->bits_per_row[0]).
  64 unsigned bitbuffer_manchester_decode(bitbuffer_t *inbuf, unsigned row, unsigned start,
  65                                      bitbuffer_t *outbuf, unsigned max);
  66
  67 // Function to compare bitbuffer rows and count repetitions
  68 int compare_rows(bitbuffer_t *bits, unsigned row_a, unsigned row_b);
  69 unsigned count_repeats(bitbuffer_t *bits, unsigned row);
  70
  71 /// Find a repeated row that has a minimum count of bits.
  72 /// Return the row index or -1.
  73 int bitbuffer_find_repeated_row(bitbuffer_t *bits, unsigned min_repeats, unsigned min_bits);
  74
  75
  76 /// Return a single bit from a bitrow at bit_idx position
  77 static inline uint8_t bitrow_get_bit(const bitrow_t bitrow, unsigned bit_idx)
  78 {
  79         return bitrow[bit_idx >> 3] >> (7 - (bit_idx & 7)) & 1;
  80 }
  81
  82 /// Return a single byte from a bitrow at bit_idx position (which may be unaligned)
  83 static inline uint8_t bitrow_get_byte(const bitrow_t bitrow, unsigned bit_idx)
  84 {
  85         return ((bitrow[(bit_idx >> 3)] << (bit_idx & 7)) |
  86                         (bitrow[(bit_idx >> 3) + 1] >> (8 - (bit_idx & 7))));
  87 }
  88
  89 #endif /* INCLUDE_BITBUFFER_H_ */