commit c2522876d58e4fda99b87644fca9f362dad13db4
parent 9138f242ad71e949398212e19a32670699e03a8d
Author: Gerd Beuster <gerd@frombelow.net>
Date: Sun, 25 Oct 2020 12:48:45 +0100
10PRINT
Diffstat:
6 files changed, 351 insertions(+), 9 deletions(-)
diff --git a/roms/boot/boot.h b/roms/boot/boot.h
@@ -1,5 +1,14 @@
;;; Function signatures and local variables
+;;; Global zero page variables
+lfsr_state = $20 ; 16 bit
+
+;;; Temporary zero page variables;
+;;; only used in subroutine
+puts_str = $10 ; 16 bit address
+gets_len = $10 ; 8 bit
+gets_str = $11 ; 16 bit address
+
;;; init_acia
;;; Initialize acai for communication
;;; Input:
@@ -29,7 +38,6 @@
;;; Changes:
;;; a, x, y, puts_str, put_str+1
- puts_str = $10
;;; putc
;;; Send character via acia
@@ -42,7 +50,7 @@
;;; x, acai-registers
;;; puth
-;;; Convert byte two hex and send via acia
+;;; Convert byte to hex and send via acia
;;; Input:
;;; a:
;;; Byte to be printed
@@ -51,6 +59,16 @@
;;; Changes:
;;; a, x, acai-registers, c-flag
+;;; puth_nibble
+;;; Convert lower half of byte to hex and send via acia
+;;; Input:
+;;; a:
+;;; Nibble to be printed
+;;; Output:
+;;; -
+;;; Changes:
+;;; a, x, acai-registers, c-flag
+
;;; putnl
;;; Send newline via acia
;;; Input:
@@ -79,8 +97,6 @@
;;; Changes:
;;; a, y, ACAI registers
- gets_len = $10
- gets_str = $11
;;; Macros
@@ -133,6 +149,15 @@
;;; a, y, ACAI registers
+;;; PRINTNL
+;;; Send newline via acia
+;;; Input:
+;;; -
+;;; Output:
+;;; -
+;;; Changes:
+;;; a, x, acai-registers
+
#define PRINT(addr) \
.(: \
lda #<addr: \
@@ -169,5 +194,11 @@ cont: \
sta gets_len: \
jsr gets
+#define PRINTNL \
+ lda #$0d: \
+ jsr putc: \
+ lda #$0a: \
+ jsr putc
+
;;; The lines below are automatically generated by export_symbols.py
diff --git a/roms/boot/boot.s b/roms/boot/boot.s
@@ -131,19 +131,20 @@ _putc_loop:
rts
puth: ; EXPORT
- ;; Send a as hex number
+ ;; Send byte a as hex number
pha
lsr
lsr
lsr
lsr
- jsr _puth_nibble
+ jsr puth_nibble
pla
- and #$0F
- jsr _puth_nibble
+ jsr puth_nibble
rts
-_puth_nibble:
+puth_nibble: ; EXPORT
+ ;; Print hex digit
clc
+ and #$0F
adc #$30 ; Decimal number
cmp #$3A ; >10 ?
bmi _puth_putc
@@ -186,7 +187,51 @@ terminate_string:
rts
.)
+;;; 16 Bit Galouis LFSR
+;;; If you use the whole state as RNG, the quality of the
+;;; random numbers is rather poor. Just extracting one
+;;; bit from the state yields random numbers with reasonable
+;;; statistical properties.
+ lfsr_seed = $beef
+init_lfsr: ; EXPORT
+ .(
+ lda #<lfsr_seed
+ sta lfsr_state
+ lda #>lfsr_seed
+ sta lfsr_state+1
+ .)
+lfsr: ; EXPORT
+ .(
+ asl lfsr_state
+ lda lfsr_state+1
+ rol
+ bcc cont
+ eor #$0b
+cont:
+ sta lfsr_state+1
+ lda lfsr_state
+ adc #$00
+ sta lfsr_state
+ rts
+ .)
+#ifdef TESTS
+;;; Test function for LFSR
+test_lfsr:
+ .(
+loop:
+ jsr lfsr
+ lda lfsr_state+1
+ jsr puth
+ lda lfsr_state
+ jsr puth
+ PRINTSNL("")
+ jsr getc
+ jmp loop
+ .)
+#endif // TESTS
+
+
;;; Vectors
.dsb $fffa-*, $ff
.word $0000 ; nmi
diff --git a/sw/10print/10print.s b/sw/10print/10print.s
@@ -0,0 +1,30 @@
+#include "../../roms/boot/liba.h"
+
+ * = $0300
+init:
+ cld
+ jsr init_acia
+ jsr init_lfsr
+ jmp ten_print
+
+ten_print:
+ .(
+ ldx #$10
+l1:
+ ldy #$00
+l0:
+ dey
+ bne l0
+ dex
+ bne l1
+ jsr lfsr
+ and #$01
+ bne slash
+ PRINTS('╲')
+ jsr putc
+ jmp ten_print
+slash:
+ PRINTS('╱')
+ jsr putc
+ jmp ten_print
+ .)
diff --git a/sw/10print/Makefile b/sw/10print/Makefile
@@ -0,0 +1,16 @@
+TARGET=10print.bin
+TARGET_BASENAME=$(basename $(TARGET))
+
+all: $(TARGET) $(TARGET_BASENAME)_symon.bin
+
+%.bin: %.s
+ xa -l "$(basename $@).l" -r -o "$@" "$<"
+
+%_symon.bin: %.s
+ xa -DSYMON -l "$(basename $@).l" -r -o "$@" "$<"
+
+upload: $(TARGET)
+ ../../roms/boot/boot.py $(TARGET)
+
+clean:
+ rm -f *.bin *.l
diff --git a/sw/10print/lfsr.py b/sw/10print/lfsr.py
@@ -0,0 +1,64 @@
+#!/usr/bin/env python3
+"""Script to find constants for LSFR and to generate test values."""
+
+import pdb
+
+def find_poly():
+ for p in range(0x100):
+ poly = p * 0x100
+ start = 0xBEEF
+ state = start
+ period = 0
+ while True:
+ # print("0x{:04x}".format(state))
+ state <<= 1
+ if (state >> 16) == 1:
+ state ^= poly
+ state += 1
+ state &= 0xFFFF
+ if state == start:
+ break
+ period += 1
+ print("0x{:04X}: {}".format(poly, period))
+
+
+class LFSR:
+ def __init__(self, state=0xBEEF, polynomial=0x0B00):
+ self.state = state
+ self.polynomial = polynomial
+
+ def getBit(self):
+ self.state <<= 1
+ if (self.state >> 16) == 1:
+ self.state ^= self.polynomial
+ self.state += 1
+ self.state &= 0xFFFF
+ return (self.state & 1)
+
+ def getByte(self):
+ res = 0
+ for _ in range(8):
+ res <<= 1
+ res += self.getBit()
+ return bytes([res])
+
+def check_poly(poly):
+ state = 0xBEEF
+ for _ in range(65535):
+ state <<= 1
+ if (state >> 16) == 1:
+ state ^= poly
+ state += 1
+ state &= 0xFFFF
+ print("0x{:04X}".format(state))
+
+def write_random_numbers():
+ with open('random.dat', 'wb') as f:
+ l = LFSR()
+ for _ in range(2500):
+ f.write(l.getByte())
+
+if __name__ == '__main__':
+ # find_poly()
+ check_poly(0x0B00)
+ # write_random_numbers()
diff --git a/sw/10print/test_rng.py b/sw/10print/test_rng.py
@@ -0,0 +1,156 @@
+#!/usr/bin/env python2
+
+"""FIPS 140-2: RNG Power-Up Tests"""
+
+# Asses the quality of your TRNG by running the statistical random
+# number generator tests from Chapter 4.9.1 (Power-Up Tests) of "FIPS
+# PUB 140-2 - SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC MODULES". The
+# document is available on the handout server.
+
+FILENAME='random.dat'
+#FILENAME='random_radio_noise.dat'
+
+def readRandomBits(filename):
+ """Read file and return it as list of bits."""
+ rn = []
+ rnFile = open(filename, 'rb')
+ rn = map(ord, rnFile.read())
+ rnFile.close()
+ return(reduce(lambda x,y: x+int2bin(y,8), rn, []))
+
+def int2bin(x, n):
+ """Convert integer to array of bits.
+
+ x : integer
+ n : length of bit array"""
+ b = map(lambda x: ord(x)-ord('0'), list(bin(x)[2:]))
+ return([0]*(n-len(b)) + b)
+
+def bin2int(b):
+ """Convert array of bits to integer."""
+ return(int("".join(map(lambda x: chr(x+ord('0')), b)), 2))
+
+def testRandomNumbers(randomBits):
+ print('Monobit Test: %s' % repr(monobitTest(randomBits)))
+ print('Poker Test: %s' % repr(pokerTest(randomBits)))
+ print('Runs Test: %s' % repr(runsTest(randomBits)))
+ print('Long Runs Test: %s' % repr(longRunsTest(randomBits)))
+
+def monobitTest(randomBits):
+ """FIPS 140-2 monobit test"""
+ # Count the number of ones in the 20,000 bit stream. Denote this
+ # quantity by x.
+ #
+ # The test is passed if 9725 < x < 10275
+ pass
+## BEGIN CODE SNIPPET ASSIGNMENT
+ x = sum(randomBits)
+ return((9725 < x) and (x < 10275))
+## END CODE SNIPPET
+
+def pokerTest(randomBits):
+ """FIPS 140-2 poker test"""
+ # Divide the 20000 bit stream into 5000 contiguous 4 bit
+ # segments. Count and store the number of occurrences of the 16
+ # possible 4 bit values. Denote f[i] as the number of each 4 bit
+ # value i where 0 < i < 15.
+ #
+ # Evaluate the following:
+ # 15
+ # --
+ # x = (16/5000) * ( \ f[i]^2 ) - 5000
+ # /
+ # --
+ # i=0
+ #
+ # The test is passed if 2.16 < x < 46.17
+ #
+ # See fips_140_2.pdf, page 39-40
+ pass
+## BEGIN CODE SNIPPET ASSIGNMENT
+ f = [0]*16
+ for i in xrange(0, len(randomBits), 4):
+ f[bin2int(randomBits[i:i+4])] += 1
+ cum = sum(map(lambda x: x*x, f))
+ x = 16.0/5000*cum-5000
+ return((2.16 < x) and (x < 46.17))
+## END CODE SNIPPET
+
+def runsTest(randomBits):
+ """FIPS 140-2 runs test"""
+ # A run is defined as a maximal sequence of consecutive bits of
+ # either all ones or all zeros that is part of the 20000 bit
+ # sample stream. The incidences of runs (for both consecutive
+ # zeros and consecutive ones) of all lengths (>= 1) in the
+ # sample stream should be counted and stored.
+ #
+ # The test is passed if the runs that occur (of lengths 1 through
+ # 6) are each within the corresponding interval specified in the
+ # table below. This must hold for both the zeros and ones (i.e.,
+ # all 12 counts must lie in the specified interval). For the
+ # purposes of this test, runs of greater than 6 are considered to
+ # be of length 6.
+ #
+ # Length Required Interval
+ # of Run
+ # 1 2343 - 2657
+ # 2 1135 - 1365
+ # 3 542 - 708
+ # 4 251 - 373
+ # 5 111 - 201
+ # 6+ 111 - 201
+ #
+ # See fips_140_2.pdf, page 40
+ pass
+## BEGIN CODE SNIPPET ASSIGNMENT
+ lowerLimits = [0, 2343, 1135, 542, 251, 111, 111]
+ upperLimits = [25000, 2657, 1365, 708, 373, 201, 201]
+ runs = [[0]*7]+[[0]*7]
+ currentRun = 0
+ for target in [0,1]:
+ for i in randomBits:
+ if(i == target):
+ currentRun += 1
+ if(currentRun > 6):
+ currentRun = 6
+ else:
+ runs[target][currentRun] += 1
+ currentRun = 0
+ # Do not forget the last run!
+ if(currentRun != 0):
+ runs[target][currentRun] += 1
+ return(all(map(lambda (x,y): x >= y, zip(runs[0], lowerLimits)))
+ and
+ all(map(lambda (x,y): x <= y, zip(runs[0], upperLimits)))
+ and
+ all(map(lambda (x,y): x >= y, zip(runs[1], lowerLimits)))
+ and
+ all(map(lambda (x,y): x <= y, zip(runs[1], upperLimits))))
+
+## END CODE SNIPPET
+
+def longRunsTest(randomBits):
+ """FIPS 140-2 long runs test"""
+ # A long run is defined to be a run of length 26 or more (of
+ # either zeros or ones). On the sample of 20000 bits, the test is
+ # passed if there are no long runs.
+ #
+ # See fips_140_2.pdf, page 40
+ pass
+## BEGIN CODE SNIPPET ASSIGNMENT
+ for target in [0,1]:
+ currentRun = 0
+ for i in randomBits:
+ if(i == target):
+ currentRun += 1
+ if(currentRun == 26):
+ return(False)
+ else:
+ currentRun = 0
+ return(True)
+## END CODE SNIPPET
+
+
+if __name__ == "__main__":
+ randomBits = readRandomBits(filename=FILENAME)
+ testRandomNumbers(randomBits=randomBits)
