Skip to content

C Puzzle

Jump to bottom
Julian Kemmerer edited this page Oct 1, 2023 · 36 revisions

Problem

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

Constraints

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 +=1 or -=1 instead of ++ or --
  • Use bool|u/int_t types
  • 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;
}

Test

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

What's going on here?

Why is this a page on a hardware description language wiki?

Read this and see if it sounds familiar at all 😏

Solutions

This puzzle is the same problem present in digital universal asynchronous receivers(/transmitters) UART. N=one half of one bit period in time. 2N=uart bit period, 3N is skipping 1.5 bits to get into center of bit for sampling (minus 1 is for counting/off by one reasons). Units are your clock cycle time (ex. 100MHz = 10ns per tick, per run of function).

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 operation's 'box'/node in the graph is scaled to the time+space requirement of the computation ~+ combinatorial delay x a rough estimate of size based on number of IO wires (TODO measuring/optimizing for fewer registers/LUTs).

First New Solution

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':

picture of solution1 code

Dataflow: solution1 dataflow graph

In the the above dataflow graph, some of the larger and first items you see should be:

  • BIN_OP_SL_uint8_t_uint32_t line 112 4.4ns
  • BIN_OP_PLUS_int32_t_int33_t line 109 2.9ns

After synthesizing for an example Xilinx Artix 7 part, Vivado logs produced by the tool show how the_function has an operating frequency of ~ 142 MHz:

Report Cell Usage: 
+------+-------+------+
|      |Cell   |Count |
+------+-------+------+
|1     |CARRY4 |    43|
|2     |LUT1   |     5|
|3     |LUT2   |     2|
|4     |LUT4   |    18|
|5     |LUT5   |    40|
|6     |LUT6   |    55|
|7     |FDRE   |   113|
+------+-------+------+

  Source:                 the_function_0CLK_a6fd0288/bit_pos_reg[4]/C
  Destination:            return_output_output_reg_reg[0]/R
  Data Path Delay:        6.522ns  (logic 2.414ns (37.013%)  route 4.108ns (62.987%))
  Logic Levels:           9  (CARRY4=6 LUT4=1 LUT5=1 LUT6=1)

TODO

Original Solution

picture of solution0 code

TODO

Clone this wiki locally