C Puzzle
Imagine a sequence of zeros and ones: 1,1,0,1,0,0,1 etc
Binary bytes (ASCII characters) have been encoded into the sequence based on some given integer constant N(ex.=1,2,etc) as follows:
- The sequence begins with 2N or more 1's
- Upon seeing the first 1->0 transition skip the next 3N-1 values
- The value arrived at is the first and least significant bit in the byte
- The next seven more-significant bits of the byte are obtained by skipping every 2N-1 values
- After the 8th bit completing the byte, repeat the above for next byte, beginning with looking for the 1->0 transition
Fill in this C function such that it returns zero/NULL until a full eight bit byte/character is parsed.
- The function is run once for each element in the sequence in order
- Only add code inside the function
- Only return a completed non-zero/null character once
- Use a single return statement at the end of the function
- No global variables, no pointers, pass by value only
- No libraries, no OS functionality, etc
- Use
+=1or-=1instead of++or-- - Use
bool|u/int_ttypes - Hint: static local variables maintain state
uint8_t the_function(bool seq_val){
uint8_t return_value = 0;
// CODE HERE
// One return statement at end of function
return return_value;
}You can compile and run your version of the_function (along with a working solution) as shown in c_puzzle.c:
Set #define N to either 1 or 2. The input_values array sequences encodes two characters "Hi".
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define N 2 // Some integer ex. 1,2
#define SKIP3 ((3*N)-1)
#define SKIP2 ((2*N)-1)
uint8_t the_function(bool seq_val){
// Hint: static uint8_t char_buffer; // Buffer to hold eight bits
uint8_t return_value = 0;
// CODE HERE
// One return statement at end of function
return return_value;
}
// Wrapper function for unrelated reasons...
void testbench(){
// These input_values sequences encode "Hi" with N=1 or N=2
#if N==1
// N=1
#define TEST_SIZE 45
bool input_values[TEST_SIZE] = {
1, // 2*N=2 or more 1's to start
1, // Ex. 3
1,
//
0, // The 1->0 transition \/
0, // Skip 3*N - 1=2
// 'H' = 0x48 = 0b01001000
0, // Skipped
0, // Bit[0]
//
0, // Skip 2*N - 1=1
0, // Bit[1]
//
0, // Skip 2*N - 1=1
0, // Bit[2]
//
1, // Skip 2*N - 1=1
1, // Bit[3]
//
0, // Skip 2*N - 1=1
0, // Bit[4]
//
0, // Skip 2*N - 1=1
0, // Bit[5]
//
1, // Skip 2*N - 1=1
1, // Bit[6]
//
0, // Skip 2*N - 1=1
0, // Bit[7]
//
1, // 2*N=2 or more 1's
1, // Ex. 3
1,
//
0, // The 1->0 transition \/
0, // Skip 3*N - 1=2
// 'i' = 0x69 = 0b01101001
1, // Skipped
1, // Bit[0]
//
0, // Skip 2*N - 1=1
0, // Bit[1]
//
0, // Skip 2*N - 1=1
0, // Bit[2]
//
1, // Skip 2*N - 1=1
1, // Bit[3]
//
0, // Skip 2*N - 1=1
0, // Bit[4]
//
1, // Skip 2*N - 1=1
1, // Bit[5]
//
1, // Skip 2*N - 1=1
1, // Bit[6]
//
0, // Skip 2*N - 1=1
0, // Bit[7]
//
1, // 2*N=2 or more 1's
1, //
1
};
#endif
#if N==2
// N=2
#define TEST_SIZE 87
bool input_values[TEST_SIZE] = {
1, // 2*N=4 or more 1's to start
1, // Ex. 5
1,
1,
1,
//
0, // The 1->0 transition \/
0, // Skip 3*N - 1=5
0, // Skipped
0, // Skipped
// 'H' = 0x48 = 0b01001000
0, // Skipped
0, // Skipped
0, // Bit[0]
0, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[1]
0, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[2]
0, // Skip 2*N - 1=3
//
1, // Skipped
1, // Skipped
1, // Bit[3]
1, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[4]
0, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[5]
0, // Skip 2*N - 1=3
//
1, // Skipped
1, // Skipped
1, // Bit[6]
1, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[7]
0,
//
1, // 2*N=4 or more 1's
1, // Ex. 5
1,
1,
1,
//
0, // The 1->0 transition \/
0, // Skip 3*N - 1=5
0, // Skipped
0, // Skipped
// 'i' = 0x69 = 0b01101001
1, // Skipped
1, // Skipped
1, // Bit[0]
1, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[1]
0, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[2]
0, // Skip 2*N - 1=3
//
1, // Skipped
1, // Skipped
1, // Bit[3]
1, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[4]
0, // Skip 2*N - 1=3
//
1, // Skipped
1, // Skipped
1, // Bit[5]
1, // Skip 2*N - 1=3
//
1, // Skipped
1, // Skipped
1, // Bit[6]
1, // Skip 2*N - 1=3
//
0, // Skipped
0, // Skipped
0, // Bit[7]
0,
//
1, // 2*N=4 or more 1's
1, // Ex. 5
1,
1,
1
};
#endif
static uint32_t seq_index = 0;
uint8_t the_char = the_function(input_values[seq_index]);
if(the_char != 0){
printf("the_char = %c\n", the_char);
}
seq_index += 1;
}
// gcc c_puzzle.c -o c_puzzle && ./c_puzzle
int main(int argc, char** argv)
{
int i = 0;
while(i<TEST_SIZE)
{
testbench();
i++;
}
return 0;
}Expected output:
the_char = H
the_char = i
Why is this a page on a hardware description language wiki?
Read this and see if it sounds familiar at all 😏
C code in c_puzzle.c written to solve this puzzle can be used with the PipelineC tool (see comments in code).
Looking at the examples/c_puzzle.c/the_function/pipeline_map.gv.png dataflow graph you can see how each operation maps to which locations in the C code. The size of each operations 'box'/node in the graph is scaled to the time+space requirement of the computation, combinatorial delay ~ a rough estimate of size based on number of IO wires (TODO measuring/optimizing for fewer registers/LUTs).
This solution was submitted by another person and not intended to target hardware, so it makes a great experiment for evaluating 'what is natural for software folks to write' vs. 'what hardware it makes':
Dataflow:
The above dataflow graph is output from the Pipelinec
TODO
TODO