[openfirmware] [commit] r2377 - forth/lib
repository service
svn at openfirmware.info
Sat Jul 16 14:05:43 CEST 2011
Author: wmb
Date: Sat Jul 16 14:05:42 2011
New Revision: 2377
URL: http://tracker.coreboot.org/trac/openfirmware/changeset/2377
Log:
Checked in linear feedback shift register code, unused at present, but related code is in cpu/arm/memtest.fth .
Added:
forth/lib/lfsr.fth
Added: forth/lib/lfsr.fth
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ forth/lib/lfsr.fth Sat Jul 16 14:05:42 2011 (r2377)
@@ -0,0 +1,238 @@
+\ See license at end of file
+purpose: Linear feedback shift register code and related memory tests
+
+0 value lfsr-state
+
+0 value lfsr-poly
+: lfsr-step ( state -- state' )
+ dup 2/ swap 1 and if lfsr-poly xor then
+;
+
+[ifdef] arm-assembler
+code lfsr-step ( state -- state' )
+ movs tos,tos,lsr #1
+ u>= if \ Carry set
+ set r0,`'user# lfsr-poly`
+ ldr r0,[up,r0]
+ eor tos,tos,r0
+ then
+c;
+code lfsr-fill ( adr seed polynomial -- adr' )
+ \ tos:polynomial
+ ldmia sp!,{r0,r1} \ r0:seed r1:adr
+ mov r2,r0 \ r2:lfsr
+ begin
+ str r2,[r1],#4
+ movs r2,r2,lsr #1
+ eorcs r2,r2,tos
+ cmp r2,r0
+ = until
+ mov tos,r1
+c;
+code random-fill ( adr len data index polynomial -- )
+ ldmia sp!,{r1,r2,r3,r4} \ tos:poly r1:index r2:data r3:len r4:adr
+
+ movs r3,r3,lsr #2 \ Convert to longword count
+ nxteq
+
+ sub r0,r3,#1 \ r0:remaining count
+
+ \ r3:address-lfsr r4:data-lfsr r5:data-poly
+ set r5,#0x80200003 \ 32-bit polynomial
+
+ begin
+ \ Compute new data value with an LFSR step
+ movs r2,r2,lsr #1
+ eorcs r2,r2,r5
+
+ \ Compute new address index, discarding values >= len
+ begin
+ movs r1,r1,lsr #1
+ eorcs r1,r1,tos
+ cmp r1,r3
+ u< until
+
+ \ Write the "random" value to the "random" address (adr[index])
+ str r2,[r4,r1,lsl #2]
+
+ decs r0,#1
+ 0= until
+
+ pop tos,sp
+c;
+code random-check ( adr len data index remain polynomial -- false | adr len data index remain true )
+ ldmia sp!,{r0,r1,r2,r3,r4} \ tos:poly r0:remain r1:index r2:data r3:len r4:adr
+
+ cmp r0,#0
+ moveq tos,#0 \ Return false
+ nxteq
+
+ mov r7,r3,lsr #2 \ Convert to longword count
+
+ set r5,#0x80200003 \ 32-bit polynomial
+
+ begin
+ \ Compute new data value with an LFSR step
+ movs r2,r2,lsr #1
+ eorcs r2,r2,r5
+
+ \ Compute new address index, discarding values >= len
+ begin
+ movs r1,r1,lsr #1
+ eorcs r1,r1,tos
+ cmp r1,r7
+ u< until
+
+ \ Read the value at the "random" address (adr[index])
+ ldr r6,[r4,r1,lsl #2]
+
+ \ Compare it to the calculated value
+ cmp r6,r2
+
+ decne r0,#1
+ stmnedb sp!,{r0,r1,r2,r3,r4} \ Push results
+ mvnne tos,#0 \ True on top of stack
+ nxtne
+
+ decs r0,#1
+ 0= until
+
+ mov tos,#0
+c;
+[then]
+0 [if] \ This is for testing the period of various polynomials
+code lfsr-period ( polynomial -- period )
+ \ tos:polynomial
+ mov r0,#1 \ r0:seed
+ mov r2,r0 \ r2:lfsr
+ mov r1,#0 \ r1:count
+ begin
+ inc r1,#1
+ movs r2,r2,lsr #1
+ eorcs r2,r2,tos
+ cmp r2,r0
+ = until
+ mov tos,r1
+c;
+[then]
+[then]
+[ifdef] x86-assembler
+code lfsr-step ( state -- state' )
+ ax pop
+ 1 # ax shr
+ carry? if
+ 'user lfsr-poly bx mov
+ bx ax xor
+ then
+ ax push
+c;
+[then]
+
+0 [if]
+\ Given a list of bit numbers for the polynomial taps, compute the mask value
+\ If the polynomial is x^15 + x^14 + 1, the bit numbers are 15, 14, and 0, so
+\ the argument list would be 0 14 15 . The 0 must be first to end the list.
+\ The order of the others is irrelevant.
+: bits>poly ( 0 bit#0 ... bit#n -- mask )
+ 0 begin ( 0 bit#0 ... bit#m mask )
+ over ( 0 bit# ... bit#m mask bit#m )
+ while ( 0 bit#0 ... bit#m mask )
+ 1 rot 1- lshift or ( 0 bit#0 ... bit#m-1 mask' )
+ repeat ( 0 mask )
+ nip ( mask )
+;
+[then]
+
+\ Polynomials for maximal length LFSRs for different bit lengths
+\ The values come from the Wikipedia article for Linear Feedback Shift Register and from
+\ http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
+create polynomials \ #bits period
+h# 0 , \ 0 0
+h# 1 , \ 1 1
+h# 3 , \ 2 3
+h# 6 , \ 3 7
+h# c , \ 4 f
+h# 14 , \ 5 1f
+h# 30 , \ 6 3f
+h# 60 , \ 7 7f
+h# b8 , \ 8 ff
+h# 110 , \ 9 1ff
+h# 240 , \ 10 3ff
+h# 500 , \ 11 7ff
+h# e08 , \ 12 fff
+h# 1c80 , \ 13 1fff
+h# 3802 , \ 14 3fff
+h# 6000 , \ 15 7fff
+h# b400 , \ 16 ffff
+h# 12000 , \ 17 1ffff
+h# 20400 , \ 18 3ffff
+h# 72000 , \ 19 7ffff
+h# 90000 , \ 20 fffff
+h# 140000 , \ 21 1fffff
+h# 300000 , \ 22 3fffff
+h# 420000 , \ 23 7fffff
+h# e10000 , \ 24 ffffff
+h# 1200000 , \ 25 1ffffff
+h# 2000023 , \ 26 3ffffff
+h# 4000013 , \ 27 7ffffff
+h# 9000000 , \ 28 fffffff
+h# 14000000 , \ 29 1fffffff
+h# 20000029 , \ 30 3fffffff
+h# 48000000 , \ 31 7fffffff
+h# 80200003 , \ 32 ffffffff
+
+: round-up-log2 ( n -- log2 )
+ dup log2 ( n log2 )
+ tuck 1 swap lshift ( log2 n 2^log2 )
+ > - ( log2' )
+;
+
+defer .lfsr-mem-error
+: (.lfsr-mem-error) ( adr len data index remain -- adr len data index remain )
+ push-hex
+ ." Error at address " 4 pick 2 pick la+ dup 8 u.r ( adr len data index remain err-adr )
+ ." - expected " 3 pick 8 u.r ( adr len data index remain err-adr )
+ ." got " l@ 8 u.r cr
+ pop-base
+;
+' (.lfsr-mem-error) to .lfsr-mem-error
+: random-test ( adr len -- )
+ dup /l <= if 2drop exit then ( adr len #bits )
+ dup /l / round-up-log2 ( adr len #bits )
+ polynomials swap la+ l@ ( adr len polynomial )
+
+ 3dup 1 1 rot random-fill ( adr len polynomial )
+
+ >r ( adr len r: polynomial )
+ 1 1 third /l / 1- ( adr len data index remain r: polynomial )
+ begin ( adr len data index remain r: polynomial )
+ r@ random-check ( false | adr len data index remain true r: polynomial )
+ while ( adr len data index remain r: polynomial )
+ .lfsr-mem-error ( adr len data index remain r: polynomial )
+ repeat ( r: polynomial )
+ r> drop
+;
+
+\ LICENSE_BEGIN
+\ Copyright (c) 2010 FirmWorks
+\
+\ Permission is hereby granted, free of charge, to any person obtaining
+\ a copy of this software and associated documentation files (the
+\ "Software"), to deal in the Software without restriction, including
+\ without limitation the rights to use, copy, modify, merge, publish,
+\ distribute, sublicense, and/or sell copies of the Software, and to
+\ permit persons to whom the Software is furnished to do so, subject to
+\ the following conditions:
+\
+\ The above copyright notice and this permission notice shall be
+\ included in all copies or substantial portions of the Software.
+\
+\ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+\ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+\ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+\ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+\ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+\ OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+\ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+\
+\ LICENSE_END
More information about the openfirmware
mailing list