#!/usr/bin/ruby

def extended_gcd(a, b)
  # compute x, y, and g s.t. a * x + b * y = g = gcd (a, b)
  x = 0; x0 = 1
  y = 1; y0 = 0

  while b != 0
    q = a / b; r = a % b

    a = b; b = r
    x1 = (x0 - q * x); x0 = x; x = x1
    y1 = (y0 - q * y); y0 = y; y = y1
  end

  return [x0, y0, a]
end


def inverse_mod(a, m)
  res = extended_gcd(a, m)
  x = res[0]; q = res[1]; gcd = res[2]

  if gcd == 1
    (x + m) % m
  else 0 end
end


def bbs(x, m, n)
  l = []
  (0 ... n).each { |i|
    w = 0
    (0 ... 32).each { |j|
      x = (x * x) % m
      if (x & 1 == 1)
        w |= (1 << j)
      end
    }
    l << w
  }
  l
end


def alpha(a, m)
  m - extended_gcd(a, m)[0]
end


def words(x, n)
  s = ""
  (0 ... n).each { |i|
    s << "	.word	#{x % (2 ** 32)}\n"
    x /= (2 ** 32)
  }
  s
end


def bbs_asm_gen (x, m, k, n)

  a = alpha(m, 2 ** 32)
  b = (1 << (32 * 2 * k)) % m
  res = bbs(x, m, n).map! { |i| sprintf("%8.8x", i) }.join(" ")

  <<BBS_ASM_TXT
/* BBS in smartmips

x = #{x} ; random seed
m = #{m} ; modulus (blum number)
a = #{a} ; a = alpha s.t. m * alpha = -1 (mod 2^32)
b = #{b} ; b = (2 ^ 32 ^ 2k) mod m
k = #{k} ; k = (words of x) + 1 = (words of m) + 1 = (words of y) + 1 = words of b
n = #{n} ; n = words of L
---
expected result:
#{res}

regs <-> variables
at i
v0 L_
v1 l		; result mem area top address
a0 n		; word length of result
a1 j
a2 thirtytwo	; const 32
a3 k		; word length of X, M, Y, and beta2k
t0 alpha	; m_[0] * alpha = -1 (mod 2^32)
t1 x		; seed mem area top address
t2 y		; temp mem area top address
t3 m_		; mod mem area top address
t4 one
t5 ext
t6 int_
t7 X_
s0 Y_
s1 M_
s2 quot
s3 C
s4 t
s5 s_
s6 b2k		; & ((2^32) ^ 2) ^ k (mod m)
s7 B2K_
t8 w'
t9 w
*/

	.equ	k,	#{k}
	.equ	n,	#{n}

	.text
	.set	noat

main:
	.globl	main
init_:
	/* l : result memory area (L) top address */
	lui	$v1,%hi(L)
	addiu	$v1,$v1,%lo(L)

	/* n : word length of L */
	li	$a0, n

	/* thirtytwo */
	li	$a2, 32

	/* k : word length of X, M, Y, and beta2k */
	li	$a3, k

	/* alpha : m_[0] * alpha = -1 (mod 2^32) */
	lui	$t0,%hi(#{a})
	addiu	$t0,$t0,%lo(#{a})

	/* x : seed memory area (X) top address */
	lui	$t1,%hi(X)
	addiu	$t1,$t1,%lo(X)

	/* y : temp memory area (Y) top address */
	lui	$t2,%hi(Y)
	addiu	$t2,$t2,%lo(Y)

	/* m_ : modulus memory area (M) top address */
	lui	$t3,%hi(M)
	addiu	$t3,$t3,%lo(M)

	/* b2k : top address of memory area (B) where has 2^32 ^ 2 ^ k */
	lui	$s6,%hi(B)
	addiu	$s6,$s6,%lo(B)

bbs_asm:
/* BEGIN -- GENERATED FROM COQ IMPL. */
L0:	addiu $at, $0, 0
L1:	addiu $v0, $v1, 0
L2:	beq $at, $a0, L238
L3:	addiu $a1, $0, 0
L4:	addiu $t9, $0, 0
L5:	beq $a1, $a2, L234
L6:	addiu $s1, $t2, 0
L7:	addiu $t5, $a3, 0
L8:	beq $t5, $0, L13
L9:	sw $0, 0($s1)
L10:	addiu $s1, $s1, 4
L11:	addiu $t5, $t5, -1
L12:	b L8
L13:	mflhxu $0
L14:	mthi $0
L15:	mtlo $0
L16:	addiu $t4, $0, 1
L17:	addiu $s3, $0, 0
L18:	addiu $t5, $0, 0
L19:	beq $t5, $a3, L54
L20:	lwxs $t7, $t5($t1)
L21:	lw $s7, 0($t1)
L22:	lw $s1, 0($t2)
L23:	multu $t7, $s7
L24:	lw $s0, 0($t3)
L25:	maddu $s1, $t4
L26:	mflo $s4
L27:	mfhi $s5
L28:	multu $s4, $t0
L29:	addiu $t6, $0, 1
L30:	mflo $s2
L31:	mthi $s5
L32:	mtlo $s4
L33:	maddu $s2, $s0
L34:	mflhxu $s1
L35:	addiu $s4, $t2, 0
L36:	beq $t6, $a3, L48
L37:	lwxs $s7, $t6($t1)
L38:	lwxs $s1, $t6($t2)
L39:	maddu $t7, $s7
L40:	lwxs $s0, $t6($t3)
L41:	maddu $s1, $t4
L42:	maddu $s2, $s0
L43:	addiu $t6, $t6, 1
L44:	mflhxu $s1
L45:	addiu $s4, $s4, 4
L46:	sw $s1, -4($s4)
L47:	b L36
L48:	maddu $s3, $t4
L49:	mflhxu $s1
L50:	addiu $t5, $t5, 1
L51:	sw $s1, 0($s4)
L52:	mflhxu $s3
L53:	b L19
L54:	beq $s3, $0, L79
L55:	addiu $s4, $s4, 4
L56:	sw $s3, 0($s4)
L57:	addiu $t5, $a3, 1
L58:	addiu $t4, $0, 1
L59:	addiu $t6, $0, 0
L60:	addiu $s0, $t2, 0
L61:	addiu $s3, $0, 0
L62:	beq $t6, $t5, L78
L63:	lwxs $s1, $t6($t3)
L64:	addu $s7, $s1, $s3
L65:	sltu $s2, $s7, $s1
L66:	lwxs $s1, $t6($t2)
L67:	beq $s2, $0, L70
L68:	nop
L69:	b L74
L70:	multu $s1, $t4
L71:	msubu $s7, $t4
L72:	sltu $s3, $s1, $s7
L73:	mflhxu $s1
L74:	sw $s1, 0($s0)
L75:	addiu $s0, $s0, 4
L76:	addiu $t6, $t6, 1
L77:	b L62
L78:	b L117
L79:	addiu $t7, $a3, 0
L80:	addiu $s7, $0, 1
L81:	beq $t7, $0, L93
L82:	beq $s7, $0, L92
L83:	addiu $t7, $t7, -1
L84:	lwxs $s1, $t7($t2)
L85:	lwxs $s0, $t7($t3)
L86:	sltu $t6, $s1, $s0
L87:	movn $s7, $0, $t6
L88:	sltu $t5, $s0, $s1
L89:	movn $s7, $0, $t5
L90:	movz $s7, $0, $t7
L91:	b L82
L92:	b L94
L93:	addiu $t6, $0, 0
L94:	beq $t6, $0, L97
L95:	nop
L96:	b L117
L97:	addiu $t4, $0, 1
L98:	addiu $t6, $0, 0
L99:	addiu $t5, $t2, 0
L100:	addiu $s3, $0, 0
L101:	beq $t6, $a3, L117
L102:	lwxs $s1, $t6($t3)
L103:	addu $s7, $s1, $s3
L104:	sltu $s2, $s7, $s1
L105:	lwxs $s1, $t6($t2)
L106:	beq $s2, $0, L109
L107:	nop
L108:	b L113
L109:	multu $s1, $t4
L110:	msubu $s7, $t4
L111:	sltu $s3, $s1, $s7
L112:	mflhxu $s1
L113:	sw $s1, 0($t5)
L114:	addiu $t5, $t5, 4
L115:	addiu $t6, $t6, 1
L116:	b L101
L117:	addiu $s1, $t1, 0
L118:	addiu $t5, $a3, 0
L119:	beq $t5, $0, L124
L120:	sw $0, 0($s1)
L121:	addiu $s1, $s1, 4
L122:	addiu $t5, $t5, -1
L123:	b L119
L124:	mflhxu $0
L125:	mthi $0
L126:	mtlo $0
L127:	addiu $t4, $0, 1
L128:	addiu $s3, $0, 0
L129:	addiu $t5, $0, 0
L130:	beq $t5, $a3, L165
L131:	lwxs $s0, $t5($t2)
L132:	lw $s7, 0($s6)
L133:	lw $s1, 0($t1)
L134:	multu $s0, $s7
L135:	lw $t7, 0($t3)
L136:	maddu $s1, $t4
L137:	mflo $s4
L138:	mfhi $s5
L139:	multu $s4, $t0
L140:	addiu $t6, $0, 1
L141:	mflo $s2
L142:	mthi $s5
L143:	mtlo $s4
L144:	maddu $s2, $t7
L145:	mflhxu $s1
L146:	addiu $s4, $t1, 0
L147:	beq $t6, $a3, L159
L148:	lwxs $s7, $t6($s6)
L149:	lwxs $s1, $t6($t1)
L150:	maddu $s0, $s7
L151:	lwxs $t7, $t6($t3)
L152:	maddu $s1, $t4
L153:	maddu $s2, $t7
L154:	addiu $t6, $t6, 1
L155:	mflhxu $s1
L156:	addiu $s4, $s4, 4
L157:	sw $s1, -4($s4)
L158:	b L147
L159:	maddu $s3, $t4
L160:	mflhxu $s1
L161:	addiu $t5, $t5, 1
L162:	sw $s1, 0($s4)
L163:	mflhxu $s3
L164:	b L130
L165:	beq $s3, $0, L190
L166:	addiu $s4, $s4, 4
L167:	sw $s3, 0($s4)
L168:	addiu $t5, $a3, 1
L169:	addiu $t4, $0, 1
L170:	addiu $t6, $0, 0
L171:	addiu $t7, $t1, 0
L172:	addiu $s3, $0, 0
L173:	beq $t6, $t5, L189
L174:	lwxs $s1, $t6($t3)
L175:	addu $s7, $s1, $s3
L176:	sltu $s2, $s7, $s1
L177:	lwxs $s1, $t6($t1)
L178:	beq $s2, $0, L181
L179:	nop
L180:	b L185
L181:	multu $s1, $t4
L182:	msubu $s7, $t4
L183:	sltu $s3, $s1, $s7
L184:	mflhxu $s1
L185:	sw $s1, 0($t7)
L186:	addiu $t7, $t7, 4
L187:	addiu $t6, $t6, 1
L188:	b L173
L189:	b L228
L190:	addiu $s0, $a3, 0
L191:	addiu $s7, $0, 1
L192:	beq $s0, $0, L204
L193:	beq $s7, $0, L203
L194:	addiu $s0, $s0, -1
L195:	lwxs $s1, $s0($t1)
L196:	lwxs $t7, $s0($t3)
L197:	sltu $t6, $s1, $t7
L198:	movn $s7, $0, $t6
L199:	sltu $t5, $t7, $s1
L200:	movn $s7, $0, $t5
L201:	movz $s7, $0, $s0
L202:	b L193
L203:	b L205
L204:	addiu $t6, $0, 0
L205:	beq $t6, $0, L208
L206:	nop
L207:	b L228
L208:	addiu $t4, $0, 1
L209:	addiu $t6, $0, 0
L210:	addiu $t5, $t1, 0
L211:	addiu $s3, $0, 0
L212:	beq $t6, $a3, L228
L213:	lwxs $s1, $t6($t3)
L214:	addu $s7, $s1, $s3
L215:	sltu $s2, $s7, $s1
L216:	lwxs $s1, $t6($t1)
L217:	beq $s2, $0, L220
L218:	nop
L219:	b L224
L220:	multu $s1, $t4
L221:	msubu $s7, $t4
L222:	sltu $s3, $s1, $s7
L223:	mflhxu $s1
L224:	sw $s1, 0($t5)
L225:	addiu $t5, $t5, 4
L226:	addiu $t6, $t6, 1
L227:	b L212
L228:	lw $t8, 0($t1)
L229:	andi $t8, $t8, 1
L230:	sllv $t8, $t8, $a1
L231:	or $t9, $t9, $t8
L232:	addiu $a1, $a1, 1
L233:	b L5
L234:	sw $t9, 0($v0)
L235:	addiu $v0, $v0, 4
L236:	addiu $at, $at, 1
L237:	b L2
/* END -- GENERATED FROM COQ IMPL. */
L238:

end_:

	j	$31
	nop

	.data
X:
	.globl	X
	.align	2

#{words(x, k)}
	.word	0

M:
	.globl	M
	.align	2

#{words(m, k)}
	.word	0

L:
	.globl	L
	.align	2

#{words(0, n)}

Y:
	.globl	Y
	.align	2

#{words(0, k)}
	.word	0

B:
	.globl	B
	.align	2

#{words(b, k)}    

BBS_ASM_TXT
end


def gdb_cmd_gen(k, n)
<<GDB_CMD_TXT
target sim
set architecture mips:isa32
file a.out
load
break end_
run
x/#{k}wx &X
x/#{k}wx &M
x/#{n}wx &L
x/#{k}wx &Y
x/#{k}wx &B
info registers
GDB_CMD_TXT
end


def help()
  print <<HELP_MESSAGE
USAGE:
 -- generate assembly code of BBS --
 bbs_asm_gen.rb x m k n
  x : random seed
  m : modulus
  k : word length of x
  n : word length of result
 -- generate gdb commands --
 bbs_asm_gen.rb k n
  k : word length of x
  n : word length of result
HELP_MESSAGE
end

if (ARGV.length == 4)
  print bbs_asm_gen(ARGV[0].to_i, ARGV[1].to_i, ARGV[2].to_i, ARGV[3].to_i)
elsif (ARGV.length == 2)
  print gdb_cmd_gen(ARGV[0].to_i, ARGV[1].to_i)
else
  help()
end