gfp_generic.go 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174
  1. // +build !amd64,!arm64 generic
  2. package bn256
  3. func gfpCarry(a *gfP, head uint64) {
  4. b := &gfP{}
  5. var carry uint64
  6. for i, pi := range p2 {
  7. ai := a[i]
  8. bi := ai - pi - carry
  9. b[i] = bi
  10. carry = (pi&^ai | (pi|^ai)&bi) >> 63
  11. }
  12. carry = carry &^ head
  13. // If b is negative, then return a.
  14. // Else return b.
  15. carry = -carry
  16. ncarry := ^carry
  17. for i := 0; i < 4; i++ {
  18. a[i] = (a[i] & carry) | (b[i] & ncarry)
  19. }
  20. }
  21. func gfpNeg(c, a *gfP) {
  22. var carry uint64
  23. for i, pi := range p2 {
  24. ai := a[i]
  25. ci := pi - ai - carry
  26. c[i] = ci
  27. carry = (ai&^pi | (ai|^pi)&ci) >> 63
  28. }
  29. gfpCarry(c, 0)
  30. }
  31. func gfpAdd(c, a, b *gfP) {
  32. var carry uint64
  33. for i, ai := range a {
  34. bi := b[i]
  35. ci := ai + bi + carry
  36. c[i] = ci
  37. carry = (ai&bi | (ai|bi)&^ci) >> 63
  38. }
  39. gfpCarry(c, carry)
  40. }
  41. func gfpSub(c, a, b *gfP) {
  42. t := &gfP{}
  43. var carry uint64
  44. for i, pi := range p2 {
  45. bi := b[i]
  46. ti := pi - bi - carry
  47. t[i] = ti
  48. carry = (bi&^pi | (bi|^pi)&ti) >> 63
  49. }
  50. carry = 0
  51. for i, ai := range a {
  52. ti := t[i]
  53. ci := ai + ti + carry
  54. c[i] = ci
  55. carry = (ai&ti | (ai|ti)&^ci) >> 63
  56. }
  57. gfpCarry(c, carry)
  58. }
  59. func mul(a, b [4]uint64) [8]uint64 {
  60. const (
  61. mask16 uint64 = 0x0000ffff
  62. mask32 uint64 = 0xffffffff
  63. )
  64. var buff [32]uint64
  65. for i, ai := range a {
  66. a0, a1, a2, a3 := ai&mask16, (ai>>16)&mask16, (ai>>32)&mask16, ai>>48
  67. for j, bj := range b {
  68. b0, b2 := bj&mask32, bj>>32
  69. off := 4 * (i + j)
  70. buff[off+0] += a0 * b0
  71. buff[off+1] += a1 * b0
  72. buff[off+2] += a2*b0 + a0*b2
  73. buff[off+3] += a3*b0 + a1*b2
  74. buff[off+4] += a2 * b2
  75. buff[off+5] += a3 * b2
  76. }
  77. }
  78. for i := uint(1); i < 4; i++ {
  79. shift := 16 * i
  80. var head, carry uint64
  81. for j := uint(0); j < 8; j++ {
  82. block := 4 * j
  83. xi := buff[block]
  84. yi := (buff[block+i] << shift) + head
  85. zi := xi + yi + carry
  86. buff[block] = zi
  87. carry = (xi&yi | (xi|yi)&^zi) >> 63
  88. head = buff[block+i] >> (64 - shift)
  89. }
  90. }
  91. return [8]uint64{buff[0], buff[4], buff[8], buff[12], buff[16], buff[20], buff[24], buff[28]}
  92. }
  93. func halfMul(a, b [4]uint64) [4]uint64 {
  94. const (
  95. mask16 uint64 = 0x0000ffff
  96. mask32 uint64 = 0xffffffff
  97. )
  98. var buff [18]uint64
  99. for i, ai := range a {
  100. a0, a1, a2, a3 := ai&mask16, (ai>>16)&mask16, (ai>>32)&mask16, ai>>48
  101. for j, bj := range b {
  102. if i+j > 3 {
  103. break
  104. }
  105. b0, b2 := bj&mask32, bj>>32
  106. off := 4 * (i + j)
  107. buff[off+0] += a0 * b0
  108. buff[off+1] += a1 * b0
  109. buff[off+2] += a2*b0 + a0*b2
  110. buff[off+3] += a3*b0 + a1*b2
  111. buff[off+4] += a2 * b2
  112. buff[off+5] += a3 * b2
  113. }
  114. }
  115. for i := uint(1); i < 4; i++ {
  116. shift := 16 * i
  117. var head, carry uint64
  118. for j := uint(0); j < 4; j++ {
  119. block := 4 * j
  120. xi := buff[block]
  121. yi := (buff[block+i] << shift) + head
  122. zi := xi + yi + carry
  123. buff[block] = zi
  124. carry = (xi&yi | (xi|yi)&^zi) >> 63
  125. head = buff[block+i] >> (64 - shift)
  126. }
  127. }
  128. return [4]uint64{buff[0], buff[4], buff[8], buff[12]}
  129. }
  130. func gfpMul(c, a, b *gfP) {
  131. T := mul(*a, *b)
  132. m := halfMul([4]uint64{T[0], T[1], T[2], T[3]}, np)
  133. t := mul([4]uint64{m[0], m[1], m[2], m[3]}, p2)
  134. var carry uint64
  135. for i, Ti := range T {
  136. ti := t[i]
  137. zi := Ti + ti + carry
  138. T[i] = zi
  139. carry = (Ti&ti | (Ti|ti)&^zi) >> 63
  140. }
  141. *c = gfP{T[4], T[5], T[6], T[7]}
  142. gfpCarry(c, carry)
  143. }