randf - a fast and space-efficient 32-bit floating point RNG

randf - a fast and space-efficient 32-bit floating point RNG

Postby jar » Tue Mar 21, 2017 3:52 am

I needed a 32-bit floating point random number generator to return value from 0.0 (inclusive) to 1.0 (exclusive). I wanted it to be compact (in instruction space) and fast.

This may be considered a tutorial in low-level assembly optimization. Or you can just use the randf.S if you're looking for a RNG for Epiphany.

I began with the LFSR113 RNG, found here: http://simul.iro.umontreal.ca/rng/lfsr113.c

I modified it the file slightly to get randf.c (this should be functionally equivalent):
Code: Select all
#define SEED 987654321
float randf (void)
{
   static unsigned int zstate[4] = {SEED, SEED, SEED, SEED};
   unsigned int b;
   unsigned int z0 = zstate[0];
   unsigned int z1 = zstate[1];
   unsigned int z2 = zstate[2];
   unsigned int z3 = zstate[3];
   b  = ((z0 << 6) ^ z0) >> 13;
   z0 = ((z0 & 0xFFFFFFFEu) << 18) ^ b;
   zstate[0] = z0;
   b  = ((z1 << 2) ^ z1) >> 27;
   z1 = ((z1 & 0xFFFFFFF8u) << 2) ^ b;
   zstate[1] = z1;
   b  = ((z2 << 13) ^ z2) >> 21;
   z2 = ((z2 & 0xFFFFFFF0u) << 7) ^ b;
   zstate[2] = z2;
   b  = ((z3 << 3) ^ z3) >> 12;
   z3 = ((z3 & 0xFFFFFF80u) << 13) ^ b;
   zstate[3] = z3;
   return (z0 ^ z1 ^ z2 ^ z3) * 2.3283064e-10f;
}


I then compiled it with the command:
Code: Select all
e-gcc -O3 -mfp-mode=truncate -mprefer-short-insn-regs -c randf.c


And I dumped the binary to see what was generated...
Code: Select all
e-objdump -D randf.o

Code: Select all
Disassembly of section .text:

00000000 <randf>:
   0:   400b 0002       mov r2,0x0
   4:   400b 1002       movt r2,0x0
   8:   28c4            ldr r1,[r2,0x1]
   a:   884c 2000       ldr r12,[r2,+0x0]
   e:   1f0b 4ff2       mov r16,0xfff8
  12:   245f 4006       lsl r17,r1,0x2
  16:   5fcb 4ff2       mov r18,0xfffe
  1a:   1feb 5ff2       movt r16,0xffff
  1e:   0944            ldr r0,[r2,0x2]
  20:   70df 4406       lsl r19,r12,0x6
  24:   248f 480a       eor r17,r17,r1
  28:   045f 410a       and r16,r1,r16
  2c:   5feb 5ff2       movt r18,0xffff
  30:   69c4            ldr r3,[r2,0x3]
  32:   6e0f 488a       eor r19,r19,r12
  36:   515f 450a       and r18,r12,r18
  3a:   276f 4806       lsr r17,r17,0x1b
  3e:   005f 4806       lsl r16,r16,0x2
  42:   9e0b 2ff2       mov r12,0xfff0
  46:   040f 490a       eor r16,r17,r16
  4a:   21b6            lsl r1,r0,0xd
  4c:   9feb 3ff2       movt r12,0xffff
  50:   300b 4ff2       mov r17,0xff80
  54:   6daf 4806       lsr r19,r19,0xd
  58:   240a            eor r1,r1,r0
  5a:   825f 208a       and r12,r0,r12
  5e:   4a5f 4806       lsl r18,r18,0x12
  62:   0c76            lsl r0,r3,0x3
  64:   3feb 5ff2       movt r17,0xffff
  68:   4d0f 490a       eor r18,r19,r18
  6c:   26a6            lsr r1,r1,0x15
  6e:   018a            eor r0,r0,r3
  70:   90ff 2406       lsl r12,r12,0x7
  74:   6cdf 010a       and r3,r3,r17
  78:   860f 208a       eor r12,r1,r12
  7c:   0186            lsr r0,r0,0xc
  7e:   280f 090a       eor r1,r18,r16
  82:   6db6            lsl r3,r3,0xd
  84:   618a            eor r3,r0,r3
  86:   260f 008a       eor r1,r1,r12
  8a:   258a            eor r1,r1,r3
  8c:   200b 4002       mov r17,0x0
  90:   0457            float r0,r1
  92:   300b 5b02       movt r17,0xb080
  96:   250e            asr r1,r1,0x8
  98:   24bf 010a       sub r1,r1,r17
  9c:   485c 4000       str r18,[r2]
  a0:   08dc 4000       str r16,[r2,+0x1]
  a4:   0422            movgtu r0,r1
  a6:   200b 0002       mov r1,0x0
  aa:   300b 12f2       movt r1,0x2f80
  ae:   895c 2000       str r12,[r2,+0x2]
  b2:   00a7            fmul r0,r0,r1
  b4:   69d4            str r3,[r2,0x3]
  b6:   194f 0402       rts
  ba:   01a2    nop

Disassembly of section .data:

00000000 <zstate.1450>:
   0:   68b1            strh r3,[r2,r1]
   2:   3ade 68b1       *unknown*
   6:   3ade 68b1       *unknown*
   a:   3ade 68b1       *unknown*
   e:   3ade    *unknown*
  10:   0018


It is 188 bytes and not using many as many 16-bit instructions as it could. The compiler (e-gcc 5.4) carelessly uses many of the higher registers. I do observe that GCC 5.2 and 5.4 emit much better code than GCC 4.8.2, however. GCC 4.8.2 is 228 bytes and extra instructions.

Thinking that maybe I could help the compiler out, I rewrote the C code to look very similar to the expected assembly.

Code: Select all
#define SEED 987654321
float randf (void)
{
   unsigned int ZZ;
   static unsigned int state[4] = {SEED, SEED, SEED, SEED};
   register unsigned int  r0 __asm__("r0");
   register unsigned int  r1 __asm__("r1");
   register unsigned int  r2 __asm__("r2");
   register unsigned int* r3 __asm__("r3");
   register float f0 __asm__("r0");
   register float f1 __asm__("r1");
   r3 = state;          // mov r3, %low(state)
   r0 = r3[0];          // ldr r0, [r3, #0]
   r2 = r0 << 6;        // lsl r2, r0, #6
   r2 = r2 ^ r0;        // eor r2, r2, r0
   r2 = r2 >> 13;       // lsr r2, r2, #13
   r1 = 0xFFFFFFFEu;    // mov r1, %low(0xFFFFFFFE)
                        // movt r1, %high(0xFFFFFFFE)
   r0 = r0 & r1;        // and r0, r0, r1
   r0 = r0 << 18;       // lsl r0, r0, #18
   r0 = r0 ^ r2;        // eor r0, r0, r2
   r3[0] = r0;          // str r0, [r3, #0]
   r1 = r3[1];          // ldr r1, [r3, #1]
   r2 = r1 << 2;        // lsl r2, r1, #2
   r2 = r2 ^ r1;        // eor r2, r2, r1
   r2 = r2 >> 27;       // lsr r2, r2, #27
   ZZ = 0xFFFFFFF8u;    // mov ZZ, %low(0xFFFFFFF8)
                        // movt ZZ, %high(0xFFFFFFF8)
   r1 = r1 & ZZ;        // and r1, r1, ZZ
   r1 = r1 << 2;        // lsl r1, r1, #2
   r1 = r1 ^ r2;        // eor r1, r1, r2
   r3[1] = r1;          // str r1, [r3, #1]
   r0 = r0 ^ r1;        // eor r0, r0, r1
   r1 = r3[2];          // ldr r1, [r3, #2]
   r2 = r1 << 13;       // lsl r2, r1, #13
   r2 = r2 ^ r1;        // eor r2, r2, r1
   r2 = r2 >> 21;       // lsr r2, r2, #21
   ZZ = 0xFFFFFF0u;     // mov ZZ, %low(0xFFFFFF0)
                        // movt ZZ, %high(0xFFFFFF0)
   r1 = r1 & ZZ;        // and r1, r1, ZZ
   r1 = r1 << 7;        // lsl r1, r1, #7
   r1 = r1 ^ r2;        // eor r1, r1, r2
   r3[2] = r1;          // str r1, [r3, #2]
   r0 = r0 ^ r1;        // eor r0, r0, r1
   r1 = r3[3];          // ldr r1, [r3, #3]
   r2 = r1 << 3;        // lsl r2, r1, #3
   r2 = r2 ^ r1;        // eor r2, r2, r1
   r2 = r2 >> 12;       // lsr r2, r2, #12
   ZZ = 0xFFFFFF80u;    // mov ZZ, %low(0xFFFFFF80)
                        // movt ZZ, %high(0xFFFFFF80)
   r1 = r1 & ZZ;        // and r1, r1, ZZ
   r1 = r1 << 13;       // lsl r1, r1, #13
   r1 = r1 ^ r2;        // eor r1, r1, r2
   r0 = r0 ^ r1;        // eor r0, r0, r1
   r3[3] = r1;          // str r1, [r3, #3]
   f1 = 2.3283064e-10f; // mov r1, %low(0x2f800000)
                        // movt r1, %high(0x2f800000)
   f0 = (float)r0;      // float r0, r0
   // XXX It turns out this isn't so simple because it's an unsigned int
   f0 = f0 * f1;        // fmul r0, r0, r1
   return f0;           // rts
}


It turns out that GCC will emit almost the same exact instructions from this format compared to the original.

I then used that C code to write the assembly (almost completed except for the unsigned int to float conversion) for randf.S:

Code: Select all
   .section .text
   .balign 4
   .global   _randf
_randf:
#define ZZ ip
   mov r3, %low(_state)
   ldr r0, [r3, #0]
   lsl r2, r0, #6
   eor r2, r2, r0
   lsr r2, r2, #13
   mov r1, %low(0xFFFFFFFE)
   movt r1, %high(0xFFFFFFFE)
   and r0, r0, r1
   lsl r0, r0, #18
   eor r0, r0, r2
   str r0, [r3, #0]
   ldr r1, [r3, #1]
   lsl r2, r1, #2
   eor r2, r2, r1
   lsr r2, r2, #27
   mov ZZ, %low(0xFFFFFFF8)
   movt ZZ, %high(0xFFFFFFF8)
   and r1, r1, ZZ
   lsl r1, r1, #2
   eor r1, r1, r2
   str r1, [r3, #1]
   eor r0, r0, r1
   ldr r1, [r3, #2]
   lsl r2, r1, #13
   eor r2, r2, r1
   lsr r2, r2, #21
   mov ZZ, %low(0xFFFFFF0)
   movt ZZ, %high(0xFFFFFF0)
   and r1, r1, ZZ
   lsl r1, r1, #7
   eor r1, r1, r2
   str r1, [r3, #2]
   eor r0, r0, r1
   ldr r1, [r3, #3]
   lsl r2, r1, #3
   eor r2, r2, r1
   lsr r2, r2, #12
   mov ZZ, %low(0xFFFFFF80)
   movt ZZ, %high(0xFFFFFF80)
   and r1, r1, ZZ
   lsl r1, r1, #13
   eor r1, r1, r2
   eor r0, r0, r1
   str r1, [r3, #3]
   float r3,r0
   mov r2, %low(0xB0800000)
   movt r2, %high(0xB0800000)
   asr r1, r0, 0x8
   sub r0, r1, r2
   movlteu r0, r3
   mov r1, %low(0x2f800000)
   movt r1, %high(0x2f800000)
   fmul r0, r0, r1
   rts
   .size   _randf, .-_randf
   .section .data
   .balign 8
   .type   _state, @object
   .size   _state, 16
_state:
   .word   987654321
   .word   987654321
   .word   987654321
   .word   987654321


This assembles to 144 bytes, a savings of 44 bytes (~25% from the C code with GCC 5.4 and much better than GCC 4.8.2)

Code: Select all
Disassembly of section .text:

00000000 <_randf>:
   0:   600b 0002    mov r3,0x0
   4:   0c44         ldr r0,[r3]
   6:   40d6         lsl r2,r0,0x6
   8:   480a         eor r2,r2,r0
   a:   49a6         lsr r2,r2,0xd
   c:   3fcb 0ff2    mov r1,0xfffe
  10:   3feb 1ff2    movt r1,0xffff
  14:   00da         and r0,r0,r1
  16:   0256         lsl r0,r0,0x12
  18:   010a         eor r0,r0,r2
  1a:   0c54         str r0,[r3]
  1c:   2cc4         ldr r1,[r3,0x1]
  1e:   4456         lsl r2,r1,0x2
  20:   488a         eor r2,r2,r1
  22:   4b66         lsr r2,r2,0x1b
  24:   9f0b 2ff2    mov r12,0xfff8
  28:   9feb 3ff2    movt r12,0xffff
  2c:   265f 008a    and r1,r1,r12
  30:   2456         lsl r1,r1,0x2
  32:   250a         eor r1,r1,r2
  34:   2cd4         str r1,[r3,0x1]
  36:   008a         eor r0,r0,r1
  38:   2d44         ldr r1,[r3,0x2]
  3a:   45b6         lsl r2,r1,0xd
  3c:   488a         eor r2,r2,r1
  3e:   4aa6         lsr r2,r2,0x15
  40:   9e0b 2ff2    mov r12,0xfff0
  44:   9feb 30f2    movt r12,0xfff
  48:   265f 008a    and r1,r1,r12
  4c:   24f6         lsl r1,r1,0x7
  4e:   250a         eor r1,r1,r2
  50:   2d54         str r1,[r3,0x2]
  52:   008a         eor r0,r0,r1
  54:   2dc4         ldr r1,[r3,0x3]
  56:   4476         lsl r2,r1,0x3
  58:   488a         eor r2,r2,r1
  5a:   4986         lsr r2,r2,0xc
  5c:   900b 2ff2    mov r12,0xff80
  60:   9feb 3ff2    movt r12,0xffff
  64:   265f 008a    and r1,r1,r12
  68:   25b6         lsl r1,r1,0xd
  6a:   250a         eor r1,r1,r2
  6c:   008a         eor r0,r0,r1
  6e:   2dd4         str r1,[r3,0x3]
  70:   6057         float r3,r0
  72:   400b 0002    mov r2,0x0
  76:   500b 1b02    movt r2,0xb080
  7a:   210e         asr r1,r0,0x8
  7c:   053a         sub r0,r1,r2
  7e:   0c42         movlteu r0,r3
  80:   200b 0002    mov r1,0x0
  84:   300b 12f2    movt r1,0x2f80
  88:   00a7         fmul r0,r0,r1
  8a:   194f 0402    rts
  8e:   01a2    nop

Disassembly of section .data:

00000000 <_state>:
   0:   68b1         strh r3,[r2,r1]
   2:   3ade 68b1    *unknown*
   6:   3ade 68b1    *unknown*
   a:   3ade 68b1    *unknown*
   e:   3ade    *unknown*
  10:   0018
User avatar
jar
 
Posts: 214
Joined: Mon Dec 17, 2012 3:27 am

Re: randf - a fast and space-efficient 32-bit floating point

Postby jar » Tue Mar 21, 2017 2:24 pm

By addressing the largest instructions which were moving 32-bit constants to a high register, we can further reduce the code footprint and number of instructions. The masking operations can replace the mask with equivalent logical shifts using the lower registers. We can eliminate almost all of the 32-bit instructions.

This is the new code, randf.S:
Code: Select all
/*
 * A 32-bit floating pont random number generator [0,1) for the Adapteva Epiphany
 * Based on http://simul.iro.umontreal.ca/rng/lfsr113.c
 * float randf(void);
 */
   .section .text
   .balign 4
   .global _randf
_randf:
   mov r3, %low(_state)
   ldr r0, [r3, #0]
   lsl r2, r0, #6
   eor r2, r2, r0
   lsr r2, r2, #13
   mov r1, #0;
   sub r1, r1, #2
   and r0, r0, r1
   lsl r0, r0, #18
   eor r0, r0, r2
   str r0, [r3, #0]
   ldr r1, [r3, #1]
   lsl r2, r1, #2
   eor r2, r2, r1
   lsr r2, r2, #27
   lsr r1, r1, #3
   lsl r1, r1, #5
   eor r1, r1, r2
   str r1, [r3, #1]
   eor r0, r0, r1
   ldr r1, [r3, #2]
   lsl r2, r1, #13
   eor r2, r2, r1
   lsr r2, r2, #21
   lsr r1, r1, #4
   lsl r1, r1, #11
   eor r1, r1, r2
   str r1, [r3, #2]
   eor r0, r0, r1
   ldr r1, [r3, #3]
   lsl r2, r1, #3
   eor r2, r2, r1
   lsr r2, r2, #12
   lsr r1, r1, #7
   lsl r1, r1, #20
   eor r1, r1, r2
   eor r0, r0, r1
   str r1, [r3, #3]
   float r3,r0
   mov r2, 0x0161
   lsl r2, r2, #23
   asr r1, r0, #8
   sub r0, r1, r2
   movlteu r0, r3
   mov r1, 0x5f
   lsl r1, r1, #23
   fmul r0, r0, r1
   rts
   .size _randf, .-_randf
   .section .data
   .balign 8
   .type _state, @object
   .size _state, 16
_state:
   .word 987654321
   .word 987654321
   .word 987654321
   .word 987654321


And it assembles to 104 bytes, which is 55% of the original code generated by GCC 5.4 and 45% of the code size generated by GCC 4.8.2:
Code: Select all
Disassembly of section .text:

00000000 <_randf>:
   0:   600b 0002    mov r3,0x0
   4:   0c44         ldr r0,[r3]
   6:   40d6         lsl r2,r0,0x6
   8:   480a         eor r2,r2,r0
   a:   49a6         lsr r2,r2,0xd
   c:   2003         mov r1,0x0
   e:   2533         sub r1,r1,2
  10:   00da         and r0,r0,r1
  12:   0256         lsl r0,r0,0x12
  14:   010a         eor r0,r0,r2
  16:   0c54         str r0,[r3]
  18:   2cc4         ldr r1,[r3,0x1]
  1a:   4456         lsl r2,r1,0x2
  1c:   488a         eor r2,r2,r1
  1e:   4b66         lsr r2,r2,0x1b
  20:   2466         lsr r1,r1,0x3
  22:   24b6         lsl r1,r1,0x5
  24:   250a         eor r1,r1,r2
  26:   2cd4         str r1,[r3,0x1]
  28:   008a         eor r0,r0,r1
  2a:   2d44         ldr r1,[r3,0x2]
  2c:   45b6         lsl r2,r1,0xd
  2e:   488a         eor r2,r2,r1
  30:   4aa6         lsr r2,r2,0x15
  32:   2486         lsr r1,r1,0x4
  34:   2576         lsl r1,r1,0xb
  36:   250a         eor r1,r1,r2
  38:   2d54         str r1,[r3,0x2]
  3a:   008a         eor r0,r0,r1
  3c:   2dc4         ldr r1,[r3,0x3]
  3e:   4476         lsl r2,r1,0x3
  40:   488a         eor r2,r2,r1
  42:   4986         lsr r2,r2,0xc
  44:   24e6         lsr r1,r1,0x7
  46:   2696         lsl r1,r1,0x14
  48:   250a         eor r1,r1,r2
  4a:   008a         eor r0,r0,r1
  4c:   2dd4         str r1,[r3,0x3]
  4e:   6057         float r3,r0
  50:   4c2b 0012    mov r2,0x161
  54:   4af6         lsl r2,r2,0x17
  56:   210e         asr r1,r0,0x8
  58:   053a         sub r0,r1,r2
  5a:   0c42         movlteu r0,r3
  5c:   2be3         mov r1,0x5f
  5e:   26f6         lsl r1,r1,0x17
  60:   00a7         fmul r0,r0,r1
  62:   194f 0402    rts
  66:   01a2    nop


Is this it? Can it be compressed further?

Yes, it would appear so. Four arithmetic instructions can be converted to two bitwise logical shifts. And because the state array is 8-byte aligned, there is an opportunity to load and store a double-word of data. But because this routine needs all four r0, r1, r2, r3 registers after the first round, only the first set of two stores can be converted to a single double-word store. The result is three instructions have been shaved off and 8 bytes, bringing the routine down to 96 bytes (~51% of the original)

randf.S:
Code: Select all
   .section .text
   .balign 4
   .global _randf
_randf:
   mov r3, %low(_state)
   ldr r0, [r3, #0]
   lsl r2, r0, #6
   eor r2, r2, r0
   lsr r2, r2, #13
   lsr r0, r0, #1
   lsl r0, r0, #19
   eor r0, r0, r2
   ldr r1, [r3, #1]
   lsl r2, r1, #2
   eor r2, r2, r1
   lsr r2, r2, #27
   lsr r1, r1, #3
   lsl r1, r1, #5
   eor r1, r1, r2
   strd r0, [r3, #0]
   eor r0, r0, r1
   ldr r1, [r3, #2]
   lsl r2, r1, #13
   eor r2, r2, r1
   lsr r2, r2, #21
   lsr r1, r1, #4
   lsl r1, r1, #11
   eor r1, r1, r2
   str r1, [r3, #2]
   eor r0, r0, r1
   ldr r1, [r3, #3]
   lsl r2, r1, #3
   eor r2, r2, r1
   lsr r2, r2, #12
   lsr r1, r1, #7
   lsl r1, r1, #20
   eor r1, r1, r2
   eor r0, r0, r1
   str r1, [r3, #3]
   float r3, r0
   mov r2, 0x0161
   lsl r2, r2, #23
   asr r1, r0, #8
   sub r0, r1, r2
   movlteu r0, r3
   mov r1, 0x5f
   lsl r1, r1, #23
   fmul r0, r0, r1
   rts
   .size _randf, .-_randf
   .section .data
   .balign 8
   .type _state, @object
   .size _state, 16
_state:
   .word 987654321
   .word 987654321
   .word 987654321
   .word 987654321


And the disassembly:
Code: Select all
00000000 <_randf>:
   0:   600b 0002    mov r3,0x0
   4:   0c44         ldr r0,[r3]
   6:   40d6         lsl r2,r0,0x6
   8:   480a         eor r2,r2,r0
   a:   49a6         lsr r2,r2,0xd
   c:   0026         lsr r0,r0,0x1
   e:   0276         lsl r0,r0,0x13
  10:   010a         eor r0,r0,r2
  12:   2cc4         ldr r1,[r3,0x1]
  14:   4456         lsl r2,r1,0x2
  16:   488a         eor r2,r2,r1
  18:   4b66         lsr r2,r2,0x1b
  1a:   2466         lsr r1,r1,0x3
  1c:   24b6         lsl r1,r1,0x5
  1e:   250a         eor r1,r1,r2
  20:   0c74         strd r0,[r3]
  22:   008a         eor r0,r0,r1
  24:   2d44         ldr r1,[r3,0x2]
  26:   45b6         lsl r2,r1,0xd
  28:   488a         eor r2,r2,r1
  2a:   4aa6         lsr r2,r2,0x15
  2c:   2486         lsr r1,r1,0x4
  2e:   2576         lsl r1,r1,0xb
  30:   250a         eor r1,r1,r2
  32:   2d54         str r1,[r3,0x2]
  34:   008a         eor r0,r0,r1
  36:   2dc4         ldr r1,[r3,0x3]
  38:   4476         lsl r2,r1,0x3
  3a:   488a         eor r2,r2,r1
  3c:   4986         lsr r2,r2,0xc
  3e:   24e6         lsr r1,r1,0x7
  40:   2696         lsl r1,r1,0x14
  42:   250a         eor r1,r1,r2
  44:   008a         eor r0,r0,r1
  46:   2dd4         str r1,[r3,0x3]
  48:   6057         float r3,r0
  4a:   4c2b 0012    mov r2,0x161
  4e:   4af6         lsl r2,r2,0x17
  50:   210e         asr r1,r0,0x8
  52:   053a         sub r0,r1,r2
  54:   0c42         movlteu r0,r3
  56:   2be3         mov r1,0x5f
  58:   26f6         lsl r1,r1,0x17
  5a:   00a7         fmul r0,r0,r1
  5c:   194f 0402    rts


I believe the only place there might be room for improvement is the unsigned int to floating point conversion (lines 4a, 4e, 50, 52, and 54 in the disassembly) but I haven't thought of anything clever yet.

This demonstrates that it is possible to beat the compiler in both performance and code size by large margins if you're willing to put in a little effort. If a GCC compiler guy is reading this, maybe you could integrate some of these optimizations into the compiler :D
User avatar
jar
 
Posts: 214
Joined: Mon Dec 17, 2012 3:27 am


Return to Assembly

Who is online

Users browsing this forum: No registered users and 1 guest