[Oberon] FPGA - Bit reversal

[Alexander Ilin]

EDIT: I meant "8 lines of the 4-bit lookups", not "16 lines". Sorry for the noise.

22.09.2017, 17:29, "Alexander Ilin" <ajsoft at yandex.ru>:
> 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.
>
> ---=====---
>  Александр
> --
> Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
> https://lists.inf.ethz.ch/mailman/listinfo/oberon

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