Bit shuffling: what goes where ?

ln the last episode (Generate the Flash's contents with a recursive algorithm), I defined the general algorithm to generate the Flash's contents. It accepts arbitrary permutations. Now, the question is to generate the proper permutation vector.

From what I have coded, it is obvious that the algorithm must be taken from the hardware point of view to give the logic address. In other words, we take the list of Flash pins (in order) then lookup what it corresponds to.

At least, I did something right: bit 0 of the Flash address selects the high/low word so there is no need to recompute the logic value twice :-) The computation cost is halved again and each "leaf" of the recursive algorithm will output 4 bytes.

Now on to the other address bits:

Flash    Function
addr
 bit

 0   High/low word
 1   D09       
 2   D08
 3   D07
 4   D06
 5   D05
 6   D04
 7   D03
 8   D12
 9   D01
10   D13
11   D00
12   D14
13   D15
14   SIGNED/UNSIGNED
15   0-EXT
16   HEX/DEC
17   D10
18   D11
19   D02

Now if the mode bits (SIGN, 0ext and Hex/dec) were in the LSB, that would save even more computations (good to know for next time) but.... K.C. Lee will complain again that I over-optimise (not that he's wrong buuuut...). In the end, routing has had the last word.

Anyway the code becomes a bit more interesting because there are those 3 modes to manage, in the middle of the permutation vector. This gives me the idea to select the conversion function not with a "if" at the leaf level, but by passing a function pointer, just like the "logic" address parameter. Some may cringe but this saves some coding efforts, it is more elegant to me :-)

Once again, this is not about writing the fastest algorithm but to make the leanest conversion functions. Reducing the number of (iteratively redundant) IF statements is a high priority because it makes the code more modular. Propagating attributes in the recursive calling stack keeps the system conceptually simple and safe (no kludge), despite the increased stack occupation (which takes a toll on CPU+memory).

So where are we now ?

Hex/Dec is managed by propagating a function pointer to the conversion function. Start recursing with the HEX code, then when index 16 is found, replace the function pointer with DEC code.
Signed/Unsigned... let's keep it simple, one IF won't kill me because it will just select a little line. Another propagated parameter is added to the growing list of arguments...
0-extension : that's another matter which affects both the HEX and DEC code, which creates 2 IF in two different functions (potential bug alert). The idea is simple too : recursively propagate a "default" value of the display, which can be null or 0000. When the leaf functions will add digits, they (unconditionally) will clear the default value and overwrite the digit.

The last part tells us that writing a digit will be done by a single function, called by both HEX and DEC conversion functions. Modularity for the win :-)

Now, on to the next puzzle !

I want to reduce the number of IFs in the leaf functions and the recursive code. But the modes will require more code inside the recursive functions. Each call would require to go through a switch-case... How can this be kept to the bare minimum ?

I have come up to this system:

   // permutation of the input bits
   var BinLUT=[
     0,   // High/low word, unused
     9, 
     8,
     7,
     6,
     5,
     4,
     3,
    12,
     1,
    13,
     0,
    14,
    15,
    -1, // SIGNED/UNSIGNED
    -2, // 0-EXT
    -3, // HEX/DEC
    10,
    11,
     2 ];

The modes are coded by negative numbers so if the number is not negative, the normal (fast) code is executed, otherwise the switch-case is examined. The code becomes "table-driven", the behaviour gets defined by an array of numbers, less by the code itself. This also means that there are less places to check if the pins change.

The new recursive function becomes:

   function recurse( index, logic) {
     msg+=" "+logic;
     if (index>0) {
       var bit=BinLUT[index--];
       var mask=1 << bit;

       recurse(index, logic);
       if (bit < 0) {
         mask=0;
         // special code for the modes
       }
       recurse(index, logic|mask) );
     }
     else
       msg+="\n";
   }

There is no else. The mask is simply cleared when a mode is detected. Once again the IF is evaluated once and changes the default value of other statements.

Tests show that the "mode" is only entered very infrequently, which justifies embedding the switch-case inside a IF statement (which is easily handled by branch prediction).

A slightly diferent approach is used there:

   function recurse( index, logic, sign) {
     msg+=" "+logic;
     if (index>0){  //0) {
       var bit=BinLUT[index--];

       recurse(index, logic, sign);

       if (bit < 0) {
         msg+="\n ------ " + bit +"\n";
         // special code for the modes
         switch(bit) {
           case -1: sign=1; break;
         }
       }
       else
         logic|= 1 << bit;
       recurse(index, logic, sign);
     }
     else
       msg+="   S="+sign+"\n";
   }

I have traded the variable mask for the else. The logic address is updated only if the if is not taken.

I have added the sign parameter and it works nicely. I can test the code easily by changing the range of iteration, progressively increasing the starting value (with the initial call) and the leaf trigger (if(index>threshold))

For example, starting with the value 15 and ending at level 10, I get the following dump:

 0 0 0 0 0 0   S=0
 1   S=0
 16384 16384   S=0
 16385   S=0
 32768 32768 32768   S=0
 32769   S=0
 49152 49152   S=0
 49153   S=0

 ------ -1
 0 0 0 0   S=1
 1   S=1
 16384 16384   S=1
 16385   S=1
 32768 32768 32768   S=1
 32769   S=1
 49152 49152   S=1
 49153   S=1

 ------ -2
 0 0 0 0 0   S=0
 1   S=0
 16384 16384   S=0
 16385   S=0
 32768 32768 32768   S=0
 32769   S=0
 49152 49152   S=0
 49153   S=0

 ------ -1
 0 0 0 0   S=1
 1   S=1
 16384 16384   S=1
 16385   S=1
 32768 32768 32768   S=1
 32769   S=1
 49152 49152   S=1
 49153   S=1

Adding support for zero-extension is pretty easy: the parameter zero_ext is included in the list of arguments.

Initially, it is set to 0 (no extension) but in the switch-case, it is overwritten by a magic value (which corresponds to 0000)

   function recurse( index, logic, sign, zero_ext) {
     msg+=" "+logic;
     if (index>10){  //0) {
       var bit=BinLUT[index--];

       recurse(index, logic, sign, zero_ext);

       if (bit < 0) {
         msg+="\n ------ " + bit +"\n";
         // special code for the modes
         switch(bit) {
           case -1: sign=1;      break;
           case -2: zero_ext=42; break;
         }
       }
       else
         logic|= 1 << bit;

       recurse(index, logic, sign, zero_ext);
     }
     else
       msg+="   S="+sign+" Z="+zero_ext+"\n";
   }

Here, I have chosen an arbitrary value because it is not yet defined. I get the following test result:

 0 0 0 0 0   S=0 Z=0
 16384   S=0 Z=0
 32768 32768   S=0 Z=0
 49152   S=0 Z=0

 ------ -1
 0 0 0   S=1 Z=0
 16384   S=1 Z=0
 32768 32768   S=1 Z=0
 49152   S=1 Z=0

 ------ -2
 0 0 0 0   S=0 Z=42
 16384   S=0 Z=42
 32768 32768   S=0 Z=42
 49152   S=0 Z=42

 ------ -1
 0 0 0   S=1 Z=42
 16384   S=1 Z=42
 32768 32768   S=1 Z=42
 49152   S=1 Z=42

Excellent !

Now it's the hex/dec's turn. I have chosen the function pointer method but if decimal was not used, then a different approach would have been even more efficient. I'll describe it for the record ;-)

Decimal numbers can change the output radically if a bit is flipped (with the exception of bit 0). There is an avalanche effect. However if you change one bit of a hexadecimal number, only the corresponding digit is affected. Do you see where I'm going ?

Start from the end of the BinLUT array and look which consecutive bits form a digit (4 consecutive bits). We have a 12-13-14-15 at index 8, and 3-1-0-2 starting at index 7. In the recursive function, we can detect if index==7 and compute all those digits, overwriting the zero_ext parameter. Further down, we have the digit 7-6-5-4 at index 3, which can be evaluated too, leaving the digit 9-8-10-11 to the leaf...

This would be pretty efficient if the system only did hexadecimal (or octal) display but the decimal mode is not so kind so I'll implement that trick ... another day. For now, I only forward the "base" parameter:

function recurse( index, logic, sign, zero_ext, base) {
  if (index>0){
    var bit=BinLUT[index--];
    recurse(index, logic, sign, zero_ext, base);

    if (bit < 0) {
      switch(bit) {
        case -1: sign=1;      break;
        case -2: zero_ext=42; break;
        case -3: base=16;     break;
      }
    }
    else
      logic|= 1 << bit;
    recurse(index, logic, sign, zero_ext, base);
  }
  else
    convert(logic, base);
}

recurse(19, 0, 0, 0, 10);

So this, kids, is how I have managed to elegantly reshuffle all the address bits !

Update: it's funny but in the above code, I used an integer argument (base, either 10 or 16) for the sake of simplicity. I would relegate the function pointers for later. However in Number conversion, I realise that it's actually not a problem at all to have hex and dec converted by the same function :-) So I keep the integer parameter...

Generate the Flash's contents with a recursive algorithm

Number conversion

Discussions

Become a Hackaday.io Member