-
Notifications
You must be signed in to change notification settings - Fork 55
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 written to solve this puzzle can be used with the PipelineC tool.
Looking at the pipeline_map.log file that is output from the tool, the dataflow of operations inside the_function is listed.
C code directly maps to hardware modules and the solutions can be compared based on what hardware is synthesized.
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 makes good hardware':
TODO PICTURE