1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package gc 6 7 // Transmogrify slow integer division into fast multiplication using magic. 8 9 // argument passing to/from 10 // smagic and umagic 11 type Magic struct { 12 W int // input for both - width 13 S int // output for both - shift 14 Bad int // output for both - unexpected failure 15 16 // magic multiplier for signed literal divisors 17 Sd int64 // input - literal divisor 18 Sm int64 // output - multiplier 19 20 // magic multiplier for unsigned literal divisors 21 Ud uint64 // input - literal divisor 22 Um uint64 // output - multiplier 23 Ua int // output - adder 24 } 25 26 // magic number for signed division 27 // see hacker's delight chapter 10 28 func smagic(m *Magic) { 29 var mask uint64 30 31 m.Bad = 0 32 switch m.W { 33 default: 34 m.Bad = 1 35 return 36 37 case 8: 38 mask = 0xff 39 40 case 16: 41 mask = 0xffff 42 43 case 32: 44 mask = 0xffffffff 45 46 case 64: 47 mask = 0xffffffffffffffff 48 } 49 50 two31 := mask ^ (mask >> 1) 51 52 p := m.W - 1 53 ad := uint64(m.Sd) 54 if m.Sd < 0 { 55 ad = -uint64(m.Sd) 56 } 57 58 // bad denominators 59 if ad == 0 || ad == 1 || ad == two31 { 60 m.Bad = 1 61 return 62 } 63 64 t := two31 65 ad &= mask 66 67 anc := t - 1 - t%ad 68 anc &= mask 69 70 q1 := two31 / anc 71 r1 := two31 - q1*anc 72 q1 &= mask 73 r1 &= mask 74 75 q2 := two31 / ad 76 r2 := two31 - q2*ad 77 q2 &= mask 78 r2 &= mask 79 80 var delta uint64 81 for { 82 p++ 83 q1 <<= 1 84 r1 <<= 1 85 q1 &= mask 86 r1 &= mask 87 if r1 >= anc { 88 q1++ 89 r1 -= anc 90 q1 &= mask 91 r1 &= mask 92 } 93 94 q2 <<= 1 95 r2 <<= 1 96 q2 &= mask 97 r2 &= mask 98 if r2 >= ad { 99 q2++ 100 r2 -= ad 101 q2 &= mask 102 r2 &= mask 103 } 104 105 delta = ad - r2 106 delta &= mask 107 if q1 < delta || (q1 == delta && r1 == 0) { 108 continue 109 } 110 111 break 112 } 113 114 m.Sm = int64(q2 + 1) 115 if uint64(m.Sm)&two31 != 0 { 116 m.Sm |= ^int64(mask) 117 } 118 m.S = p - m.W 119 } 120 121 // magic number for unsigned division 122 // see hacker's delight chapter 10 123 func umagic(m *Magic) { 124 var mask uint64 125 126 m.Bad = 0 127 m.Ua = 0 128 129 switch m.W { 130 default: 131 m.Bad = 1 132 return 133 134 case 8: 135 mask = 0xff 136 137 case 16: 138 mask = 0xffff 139 140 case 32: 141 mask = 0xffffffff 142 143 case 64: 144 mask = 0xffffffffffffffff 145 } 146 147 two31 := mask ^ (mask >> 1) 148 149 m.Ud &= mask 150 if m.Ud == 0 || m.Ud == two31 { 151 m.Bad = 1 152 return 153 } 154 155 nc := mask - (-m.Ud&mask)%m.Ud 156 p := m.W - 1 157 158 q1 := two31 / nc 159 r1 := two31 - q1*nc 160 q1 &= mask 161 r1 &= mask 162 163 q2 := (two31 - 1) / m.Ud 164 r2 := (two31 - 1) - q2*m.Ud 165 q2 &= mask 166 r2 &= mask 167 168 var delta uint64 169 for { 170 p++ 171 if r1 >= nc-r1 { 172 q1 <<= 1 173 q1++ 174 r1 <<= 1 175 r1 -= nc 176 } else { 177 q1 <<= 1 178 r1 <<= 1 179 } 180 181 q1 &= mask 182 r1 &= mask 183 if r2+1 >= m.Ud-r2 { 184 if q2 >= two31-1 { 185 m.Ua = 1 186 } 187 188 q2 <<= 1 189 q2++ 190 r2 <<= 1 191 r2++ 192 r2 -= m.Ud 193 } else { 194 if q2 >= two31 { 195 m.Ua = 1 196 } 197 198 q2 <<= 1 199 r2 <<= 1 200 r2++ 201 } 202 203 q2 &= mask 204 r2 &= mask 205 206 delta = m.Ud - 1 - r2 207 delta &= mask 208 209 if p < m.W+m.W { 210 if q1 < delta || (q1 == delta && r1 == 0) { 211 continue 212 } 213 } 214 215 break 216 } 217 218 m.Um = q2 + 1 219 m.S = p - m.W 220 } 221
