[Oberon] FPGA - Bit reversal

[Chris Burrows]

> -----Original Message-----
> From: Oberon [mailto:oberon-bounces at lists.inf.ethz.ch] On Behalf Of
> Alexander Ilin
> Sent: Friday, 22 September 2017 9:05 PM
> To: ETH Oberon and related systems
> Subject: Re: [Oberon] FPGA - Bit reversal
> 
>   There is one optimization I could suggest for the code above:
> 
> PROCEDURE ReverseWord(wd: INTEGER): INTEGER;
>   VAR i: INTEGER; rwd, u: SET;
> BEGIN
>   u := SYSTEM.VAL(SET, wd);
>   rwd := {}; i := 0;
>   WHLE u # {} DO
>     IF i IN u THEN INCL(rwd, 31-i) END;
>     EXCL(u, i);
>     INC(i)
>   END
> RETURN SYSTEM.VAL(INTEGER, rwd) END ReverseWord;
> 

Another alternative is:

PROCEDURE ReverseWord (in: INTEGER): INTEGER;
VAR
  i, out: INTEGER;
BEGIN
  out := 0;
  FOR i := 0 TO 31 DO  
    out := LSL(out, 1);
    IF ODD(in) THEN INC(out) END;
    in := LSR(in, 1)
  END
  RETURN out
END ReverseWord;


However, if portability is not an issue, by far the smallest and fastest solution using Astrobe Oberon for Cortex-M targets is:

PROCEDURE* ReverseWord (in: INTEGER): INTEGER;
  RETURN SYSTEM.RBIT(in)
END ReverseWord;

It's about 10 times faster than either of the solutions above as it generates just 4 instructions. It makes use of the ARM Cortex-M 'rbit' instruction which reverses all the bits in a 32-bit word in just 1 instruction cycle - you can't get any faster than that! 

It would make an interesting student project to use Verilog to add a similar 'rbit' instruction to the RISC5 instruction set, and implement SYSTEM.RBIT in the FPGA RISC5 compiler.

Verilog has a versatile set of bit-manipulation facilities. I haven't tested it but it appears that the Verilog code for reversing bits is simply:

   result[31:0] = data[0:31]  

Regards,
Chris Burrows
CFB Software
http://www.astrobe.com