{}
#include <stdio.h>
#include <stdint.h>
/**
* Holds a single entry of our lookup table
*/
typedef struct
{
/// The total number of '101' bit patterns which appear in the byte.
/// E.g. the byte '0101 1010' would have a count of '2'.
/// We count overlapping patterns of '10101' as having a count of '2'.
uint8_t count;
/// The number of bits of a partial pattern which appear at the start of the byte.
/// If the byte starts with '01', this takes the value '2'; if the byte starts with
/// '1', this takes the value '1'.
uint8_t startPartial;
/// The number of bits of a partial pattern which appear at the end of a byte.
/// If the byte ends with '10', this takes the value '2'; if the byte ends with
/// '1', this takes the value '1'.
uint8_t endPartial;
} LookupEntry_t;
/// A lookup from byte value -> information about that value
static LookupEntry_t s_lookup[256];
static void BuildLookup(void)
{
for (int i = 0; i < 256; i++)
{
LookupEntry_t* pEntry = &s_lookup[i];
// Partial pattern at the start of the byte
if ((i & 0x80) > 0)
{
// Starts with '1'
pEntry->startPartial = 1;
}
else if ((i & 0xC0) == 0x40)
{
// Starts with '01'
pEntry->startPartial = 2;
}
// Partial pattern at the end of the byte
if ((i & 0x01) > 0)
{
// Ends with '1'
pEntry->endPartial = 1;
}
else if ((i & 0x03) == 0x02)
{
// Ends with '10'
pEntry->endPartial = 2;
}
// Number of '101' patterns which appear in the byte
for (int j = 0; j < 6; j++)
{
if (((i >> j) & 0x07) == 0x05)
{
pEntry->count++;
}
}
}
}
int main(void)
{
BuildLookup();
// 0010 1010 1000 0101
uint8_t input[] = { 0x2A, 0x85 };
uint32_t count = 0;
uint8_t prevEndPartial = 0;
for (size_t i = 0; i < sizeof(input); i++)
{
const LookupEntry_t* pEntry = &s_lookup[input[i]];
count += pEntry->count;
// If the previous byte ends with 2 bits of a pattern, and we start with 1 bits;
// or if the previous byte ends with 1 bit of a pattern and we start with 2 bits,
// then they combine to form a '101' which is bridged between the two bytes.
if ((prevEndPartial + pEntry->startPartial) == 3)
{
count++;
}
prevEndPartial = pEntry->endPartial;
}
printf("Total: %d\n", count);
return 0;
}