[Oberon] FPGA - Bit reversal

[Alexander Ilin]

22.09.2017, 15:34, "Tomas Kral" <thomas.kral at email.cz>:
> I have tried to unroll the loop, unsure if getting any performance
> benefit.
>
>   PROCEDURE ReverseWord(wd: INTEGER): INTEGER;
>     VAR i, j: INTEGER; rwd, u: SET;
>   BEGIN
>     u := SYSTEM.VAL(SET, wd); i := 0; j := 31;
>     rwd := {}; WHILE i < j DO
>       IF i IN u THEN INCL(rwd, 31-i) END;
>       IF j IN u THEN INCL(rwd, 31-j) END;
>       INC(i); DEC(j)
>     END
>   RETURN SYSTEM.VAL(INTEGER, rwd) END ReverseWord;

  With this code you have replaced half of the comparisons (in WHILE) with the same number of additional DEC operations. This means that there may not be any performance benefits, only greater code size.

  Here's a version that should perform better than the initial one, at the price of some increase in code size:

PROCEDURE ReverseWord(wd: INTEGER): INTEGER;
  VAR i: INTEGER; rwd, u: SET;
BEGIN
  u := SYSTEM.VAL(SET, wd); i := 31;
  rwd := {}; REPEAT
    IF i IN u THEN INCL(rwd, 31-i) END;
    DEC(i);
    IF i IN u THEN INCL(rwd, 31-i) END;
    DEC(i)
  UNTIL i = 0; (* zero (in)equality checks typically produce shorter code *)
RETURN SYSTEM.VAL(INTEGER, rwd) END ReverseWord;

  In this code the number of loop termination checks is reduced in half, the rest of the code runs in same time as before. The ultimate unroll would take 32 lines of IFs, or 16 lines of the 4-bit lookups.

  Again, if early termination is possible, this still looks reasonable:

PROCEDURE ReverseWord(wd: INTEGER): INTEGER;
  VAR i: INTEGER; rwd, u: SET;
BEGIN
  u := SYSTEM.VAL(SET, wd); i := 31;
  rwd := {}; WHILE u # {} DO
    IF i IN u THEN INCL(rwd, 31-i); EXCL(u, i) END;
    DEC(i);
    IF i IN u THEN INCL(rwd, 31-i); EXCL(u, i) END;
    DEC(i)
  END
RETURN SYSTEM.VAL(INTEGER, rwd) END ReverseWord;


> I need to give more thinking to lookup tables, I like 8 bit version by
> Joerg, 32 bit version seems a bit bulky and not simple.

  I would give 4-bit version a try. 8-bit lookup table would eat 256 bytes of memory, while 4-bit only takes 16, which seems like a fair trade-off.

---=====--- 
 Александр