[Oberon] FPGA - Bit reversal

[Skulski, Wojciech]

PROCEDURE ReverseWord(wd: INTEGER): INTEGER;
 VAR wst: SET; wint: INTEGER;
BEGIN
  wst := BITS (wd);
  wst := - wst;
  wint := ORD (wst)
 RETURN wint 
END ReverseWord;

This would be a possibility if BITS were part of the Oberon language. BITS is available in Component Pascal.

Perhaps the passion for pruning the language of "unnecessary embellishments" went a bit too far.

W.
________________________________________
From: Oberon [oberon-bounces at lists.inf.ethz.ch] on behalf of Alexander Ilin [ajsoft at yandex.ru]
Sent: Friday, September 22, 2017 10:31 AM
To: ETH Oberon and related systems
Subject: Re: [Oberon] FPGA - Bit reversal

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.
>
> ---=====---
>  Александр