[Oberon] FPGA - Bit reversal

[Jörg]

Hi

Your „WriteBin" could also look like this:

PROCEDURE WriteBin(wd, n: INTEGER);
	VAR i: INTEGER;
	BEGIN
		FOR i := 0 TO n-1 DO
			IF ODD(wd) THEN Out.Ch("1“) ELSE Out.Ch("0“) END;
			wd := wd DIV 2
		END;
		Out.Ln
	END WriteBin;

The fastest ReverseByte is the following;

PROCEDURE ReverseByte(wd: BYTE): BYTE;
	BEGIN
		RETURN rev8[wd]
	END ReverseByte;

„rev8“ is an ARRAY 256 OF BYTE you would have to initialize once in the beginning.
If you don’t want to spend 256 bytes of memory, you could do it in two steps like this

PROCEDURE ReverseByte(wd: BYTE): BYTE;
	BEGIN
		RETURN rev4[wd MOD 16]*16 + rev4[wd DIV 16]
	END ReverseByte;

„rev4“ is an ARRAY 16 OF BYTE you would have to initialize once in the beginning.
With a FOR loop or statically by hand:
rev4[0] := 0; rev4[1] := 8; rev4[2] := 4; rev[3] := 12; ... 
 
br
Joerg

> Am 21.09.2017 um 21:33 schrieb Tomas Kral <thomas.kral at email.cz>:
> 
> Hi,
> 
> I have been toying with bit reversals for byte and word types. Simple
> forms consist of plain shifting in sets of bits.
> 
>  PROCEDURE ReverseByte(wd: INTEGER): INTEGER;
>    VAR i: INTEGER; rbt, t, u: SET;
>  BEGIN
>    u := SYSTEM.VAL(SET, wd);
>    rbt := {}; FOR i := 0 TO 7  DO
>      t := ASR(u, i)*{0}; t := LSL(t, 7-i);
>      rbt := rbt+t;
>    END    
>  RETURN SYSTEM.VAL(INTEGER, rbt) END ReverseByte;
> 
>  (* inefficient, how to improve? *)
>  PROCEDURE ReverseWord(wd: INTEGER): INTEGER;
>    VAR i: INTEGER; rwd, t, u: SET;
>  BEGIN
>    u := SYSTEM.VAL(SET, wd);
>    rwd := {}; FOR i := 0 TO 31  DO
>      t := ASR(u, i)*{0}; t := LSL(t, 31-i);
>      rwd := rwd+t;
>    END   
>  RETURN SYSTEM.VAL(INTEGER, rwd) END ReverseWord;
> 
> More efficiency comes with some complication. Found this at
> StackOverflow.
> 
> unsigned char reverse(unsigned char b) {
>   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
>   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
>   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
>   return b;
> }
> 
> The below procedure prints byte/word in binary, seeing long strings
> of '1' and '0' for words, makes me think if BYTE type should not be
> favoured more to INTEGER on FPGA?
> 
>  (* write word [wd] in binary, n=[1..32] number of bits to print *)
>  PROCEDURE WriteBin(wd, n: INTEGER);
>    VAR i: INTEGER; ch: CHAR; t: SET;
>  BEGIN
>    FOR i := 0 TO n-1 DO
>      t := SYSTEM.VAL(SET, ASR(wd, i))*{0};
>      ch := CHR(SYSTEM.VAL(BYTE, t)+ORD("0"));
>      Texts.Write(W, ch)
>    END;
>    Texts.WriteLn(W); Texts.Append(Oberon.Log, W.buf)
>  END WriteBin;
> 
> -- 
> Tomas Kral <thomas.kral at email.cz>
> --
> Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
> https://lists.inf.ethz.ch/mailman/listinfo/oberon