1 use crate::constants::{MAX_I32_SCALE, MAX_PRECISION_I32, POWERS_10}; 2 use crate::Decimal; 3 4 #[derive(Debug)] 5 pub struct Buf12 { 6 pub data: [u32; 3], 7 } 8 9 impl Buf12 { from_dec64(value: &Dec64) -> Self10 pub(super) const fn from_dec64(value: &Dec64) -> Self { 11 Buf12 { 12 data: [value.low64 as u32, (value.low64 >> 32) as u32, value.hi], 13 } 14 } 15 from_decimal(value: &Decimal) -> Self16 pub(super) const fn from_decimal(value: &Decimal) -> Self { 17 Buf12 { 18 data: value.mantissa_array3(), 19 } 20 } 21 22 #[inline(always)] lo(&self) -> u3223 pub const fn lo(&self) -> u32 { 24 self.data[0] 25 } 26 #[inline(always)] mid(&self) -> u3227 pub const fn mid(&self) -> u32 { 28 self.data[1] 29 } 30 #[inline(always)] hi(&self) -> u3231 pub const fn hi(&self) -> u32 { 32 self.data[2] 33 } 34 #[inline(always)] set_lo(&mut self, value: u32)35 pub fn set_lo(&mut self, value: u32) { 36 self.data[0] = value; 37 } 38 #[inline(always)] set_mid(&mut self, value: u32)39 pub fn set_mid(&mut self, value: u32) { 40 self.data[1] = value; 41 } 42 #[inline(always)] set_hi(&mut self, value: u32)43 pub fn set_hi(&mut self, value: u32) { 44 self.data[2] = value; 45 } 46 47 #[inline(always)] low64(&self) -> u6448 pub const fn low64(&self) -> u64 { 49 ((self.data[1] as u64) << 32) | (self.data[0] as u64) 50 } 51 52 #[inline(always)] set_low64(&mut self, value: u64)53 pub fn set_low64(&mut self, value: u64) { 54 self.data[1] = (value >> 32) as u32; 55 self.data[0] = value as u32; 56 } 57 58 #[inline(always)] high64(&self) -> u6459 pub const fn high64(&self) -> u64 { 60 ((self.data[2] as u64) << 32) | (self.data[1] as u64) 61 } 62 63 #[inline(always)] set_high64(&mut self, value: u64)64 pub fn set_high64(&mut self, value: u64) { 65 self.data[2] = (value >> 32) as u32; 66 self.data[1] = value as u32; 67 } 68 69 // Determine the maximum value of x that ensures that the quotient when scaled up by 10^x 70 // still fits in 96 bits. Ultimately, we want to make scale positive - if we can't then 71 // we're going to overflow. Because x is ultimately used to lookup inside the POWERS array, it 72 // must be a valid value 0 <= x <= 9 find_scale(&self, scale: i32) -> Option<usize>73 pub fn find_scale(&self, scale: i32) -> Option<usize> { 74 const OVERFLOW_MAX_9_HI: u32 = 4; 75 const OVERFLOW_MAX_8_HI: u32 = 42; 76 const OVERFLOW_MAX_7_HI: u32 = 429; 77 const OVERFLOW_MAX_6_HI: u32 = 4294; 78 const OVERFLOW_MAX_5_HI: u32 = 42949; 79 const OVERFLOW_MAX_4_HI: u32 = 429496; 80 const OVERFLOW_MAX_3_HI: u32 = 4294967; 81 const OVERFLOW_MAX_2_HI: u32 = 42949672; 82 const OVERFLOW_MAX_1_HI: u32 = 429496729; 83 const OVERFLOW_MAX_9_LOW64: u64 = 5441186219426131129; 84 85 let hi = self.data[2]; 86 let low64 = self.low64(); 87 let mut x = 0usize; 88 89 // Quick check to stop us from trying to scale any more. 90 // 91 if hi > OVERFLOW_MAX_1_HI { 92 // If it's less than 0, which it probably is - overflow. We can't do anything. 93 if scale < 0 { 94 return None; 95 } 96 return Some(x); 97 } 98 99 if scale > MAX_PRECISION_I32 - 9 { 100 // We can't scale by 10^9 without exceeding the max scale factor. 101 // Instead, we'll try to scale by the most that we can and see if that works. 102 // This is safe to do due to the check above. e.g. scale > 19 in the above, so it will 103 // evaluate to 9 or less below. 104 x = (MAX_PRECISION_I32 - scale) as usize; 105 if hi < POWER_OVERFLOW_VALUES[x - 1].data[2] { 106 if x as i32 + scale < 0 { 107 // We still overflow 108 return None; 109 } 110 return Some(x); 111 } 112 } else if hi < OVERFLOW_MAX_9_HI || hi == OVERFLOW_MAX_9_HI && low64 <= OVERFLOW_MAX_9_LOW64 { 113 return Some(9); 114 } 115 116 // Do a binary search to find a power to scale by that is less than 9 117 x = if hi > OVERFLOW_MAX_5_HI { 118 if hi > OVERFLOW_MAX_3_HI { 119 if hi > OVERFLOW_MAX_2_HI { 120 1 121 } else { 122 2 123 } 124 } else if hi > OVERFLOW_MAX_4_HI { 125 3 126 } else { 127 4 128 } 129 } else if hi > OVERFLOW_MAX_7_HI { 130 if hi > OVERFLOW_MAX_6_HI { 131 5 132 } else { 133 6 134 } 135 } else if hi > OVERFLOW_MAX_8_HI { 136 7 137 } else { 138 8 139 }; 140 141 // Double check what we've found won't overflow. Otherwise, we go one below. 142 if hi == POWER_OVERFLOW_VALUES[x - 1].data[2] && low64 > POWER_OVERFLOW_VALUES[x - 1].low64() { 143 x -= 1; 144 } 145 146 // Confirm we've actually resolved things 147 if x as i32 + scale < 0 { 148 None 149 } else { 150 Some(x) 151 } 152 } 153 } 154 155 // This is a table of the largest values that will not overflow when multiplied 156 // by a given power as represented by the index. 157 static POWER_OVERFLOW_VALUES: [Buf12; 8] = [ 158 Buf12 { 159 data: [2576980377, 2576980377, 429496729], 160 }, 161 Buf12 { 162 data: [687194767, 4123168604, 42949672], 163 }, 164 Buf12 { 165 data: [2645699854, 1271310319, 4294967], 166 }, 167 Buf12 { 168 data: [694066715, 3133608139, 429496], 169 }, 170 Buf12 { 171 data: [2216890319, 2890341191, 42949], 172 }, 173 Buf12 { 174 data: [2369172679, 4154504685, 4294], 175 }, 176 Buf12 { 177 data: [4102387834, 2133437386, 429], 178 }, 179 Buf12 { 180 data: [410238783, 4078814305, 42], 181 }, 182 ]; 183 184 pub(super) struct Dec64 { 185 pub negative: bool, 186 pub scale: u32, 187 pub hi: u32, 188 pub low64: u64, 189 } 190 191 impl Dec64 { new(d: &Decimal) -> Dec64192 pub(super) const fn new(d: &Decimal) -> Dec64 { 193 let m = d.mantissa_array3(); 194 if m[1] == 0 { 195 Dec64 { 196 negative: d.is_sign_negative(), 197 scale: d.scale(), 198 hi: m[2], 199 low64: m[0] as u64, 200 } 201 } else { 202 Dec64 { 203 negative: d.is_sign_negative(), 204 scale: d.scale(), 205 hi: m[2], 206 low64: ((m[1] as u64) << 32) | (m[0] as u64), 207 } 208 } 209 } 210 211 #[inline(always)] lo(&self) -> u32212 pub(super) const fn lo(&self) -> u32 { 213 self.low64 as u32 214 } 215 #[inline(always)] mid(&self) -> u32216 pub(super) const fn mid(&self) -> u32 { 217 (self.low64 >> 32) as u32 218 } 219 220 #[inline(always)] high64(&self) -> u64221 pub(super) const fn high64(&self) -> u64 { 222 (self.low64 >> 32) | ((self.hi as u64) << 32) 223 } 224 to_decimal(&self) -> Decimal225 pub(super) const fn to_decimal(&self) -> Decimal { 226 Decimal::from_parts( 227 self.low64 as u32, 228 (self.low64 >> 32) as u32, 229 self.hi, 230 self.negative, 231 self.scale, 232 ) 233 } 234 } 235 236 pub struct Buf16 { 237 pub data: [u32; 4], 238 } 239 240 impl Buf16 { zero() -> Self241 pub const fn zero() -> Self { 242 Buf16 { data: [0, 0, 0, 0] } 243 } 244 low64(&self) -> u64245 pub const fn low64(&self) -> u64 { 246 ((self.data[1] as u64) << 32) | (self.data[0] as u64) 247 } 248 set_low64(&mut self, value: u64)249 pub fn set_low64(&mut self, value: u64) { 250 self.data[1] = (value >> 32) as u32; 251 self.data[0] = value as u32; 252 } 253 mid64(&self) -> u64254 pub const fn mid64(&self) -> u64 { 255 ((self.data[2] as u64) << 32) | (self.data[1] as u64) 256 } 257 set_mid64(&mut self, value: u64)258 pub fn set_mid64(&mut self, value: u64) { 259 self.data[2] = (value >> 32) as u32; 260 self.data[1] = value as u32; 261 } 262 high64(&self) -> u64263 pub const fn high64(&self) -> u64 { 264 ((self.data[3] as u64) << 32) | (self.data[2] as u64) 265 } 266 set_high64(&mut self, value: u64)267 pub fn set_high64(&mut self, value: u64) { 268 self.data[3] = (value >> 32) as u32; 269 self.data[2] = value as u32; 270 } 271 } 272 273 #[derive(Debug)] 274 pub struct Buf24 { 275 pub data: [u32; 6], 276 } 277 278 impl Buf24 { zero() -> Self279 pub const fn zero() -> Self { 280 Buf24 { 281 data: [0, 0, 0, 0, 0, 0], 282 } 283 } 284 low64(&self) -> u64285 pub const fn low64(&self) -> u64 { 286 ((self.data[1] as u64) << 32) | (self.data[0] as u64) 287 } 288 set_low64(&mut self, value: u64)289 pub fn set_low64(&mut self, value: u64) { 290 self.data[1] = (value >> 32) as u32; 291 self.data[0] = value as u32; 292 } 293 294 #[allow(dead_code)] mid64(&self) -> u64295 pub const fn mid64(&self) -> u64 { 296 ((self.data[3] as u64) << 32) | (self.data[2] as u64) 297 } 298 set_mid64(&mut self, value: u64)299 pub fn set_mid64(&mut self, value: u64) { 300 self.data[3] = (value >> 32) as u32; 301 self.data[2] = value as u32; 302 } 303 304 #[allow(dead_code)] high64(&self) -> u64305 pub const fn high64(&self) -> u64 { 306 ((self.data[5] as u64) << 32) | (self.data[4] as u64) 307 } 308 set_high64(&mut self, value: u64)309 pub fn set_high64(&mut self, value: u64) { 310 self.data[5] = (value >> 32) as u32; 311 self.data[4] = value as u32; 312 } 313 upper_word(&self) -> usize314 pub const fn upper_word(&self) -> usize { 315 if self.data[5] > 0 { 316 return 5; 317 } 318 if self.data[4] > 0 { 319 return 4; 320 } 321 if self.data[3] > 0 { 322 return 3; 323 } 324 if self.data[2] > 0 { 325 return 2; 326 } 327 if self.data[1] > 0 { 328 return 1; 329 } 330 0 331 } 332 333 // Attempt to rescale the number into 96 bits. If successful, the scale is returned wrapped 334 // in an Option. If it failed due to overflow, we return None. 335 // * `upper` - Index of last non-zero value in self. 336 // * `scale` - Current scale factor for this value. rescale(&mut self, upper: usize, scale: u32) -> Option<u32>337 pub fn rescale(&mut self, upper: usize, scale: u32) -> Option<u32> { 338 let mut scale = scale as i32; 339 let mut upper = upper; 340 341 // Determine a rescale target to start with 342 let mut rescale_target = 0i32; 343 if upper > 2 { 344 rescale_target = upper as i32 * 32 - 64 - 1; 345 rescale_target -= self.data[upper].leading_zeros() as i32; 346 rescale_target = ((rescale_target * 77) >> 8) + 1; 347 if rescale_target > scale { 348 return None; 349 } 350 } 351 352 // Make sure we scale enough to bring it into a valid range 353 if rescale_target < scale - MAX_PRECISION_I32 { 354 rescale_target = scale - MAX_PRECISION_I32; 355 } 356 357 if rescale_target > 0 { 358 // We're going to keep reducing by powers of 10. So, start by reducing the scale by 359 // that amount. 360 scale -= rescale_target; 361 let mut sticky = 0; 362 let mut remainder = 0; 363 loop { 364 sticky |= remainder; 365 let mut power = if rescale_target > 8 { 366 POWERS_10[9] 367 } else { 368 POWERS_10[rescale_target as usize] 369 }; 370 371 let high = self.data[upper]; 372 let high_quotient = high / power; 373 remainder = high - high_quotient * power; 374 375 for item in self.data.iter_mut().rev().skip(6 - upper) { 376 let num = (*item as u64).wrapping_add((remainder as u64) << 32); 377 *item = (num / power as u64) as u32; 378 remainder = (num as u32).wrapping_sub(item.wrapping_mul(power)); 379 } 380 381 self.data[upper] = high_quotient; 382 383 // If the high quotient was zero then decrease the upper bound 384 if high_quotient == 0 && upper > 0 { 385 upper -= 1; 386 } 387 if rescale_target > MAX_I32_SCALE { 388 // Scale some more 389 rescale_target -= MAX_I32_SCALE; 390 continue; 391 } 392 393 // If we fit into 96 bits then we've scaled enough. Otherwise, scale once more. 394 if upper > 2 { 395 if scale == 0 { 396 return None; 397 } 398 // Equivalent to scaling down by 10 399 rescale_target = 1; 400 scale -= 1; 401 continue; 402 } 403 404 // Round the final result. 405 power >>= 1; 406 let carried = if power <= remainder { 407 // If we're less than half then we're fine. Otherwise, we round if odd or if the 408 // sticky bit is set. 409 if power < remainder || ((self.data[0] & 1) | sticky) != 0 { 410 // Round up 411 self.data[0] = self.data[0].wrapping_add(1); 412 // Check if we carried 413 self.data[0] == 0 414 } else { 415 false 416 } 417 } else { 418 false 419 }; 420 421 // If we carried then propagate through the portions 422 if carried { 423 let mut pos = 0; 424 for (index, value) in self.data.iter_mut().enumerate().skip(1) { 425 pos = index; 426 *value = value.wrapping_add(1); 427 if *value != 0 { 428 break; 429 } 430 } 431 432 // If we ended up rounding over the 96 bits then we'll try to rescale down (again) 433 if pos > 2 { 434 // Nothing to scale down from will cause overflow 435 if scale == 0 { 436 return None; 437 } 438 439 // Loop back around using scale of 10. 440 // Reset the sticky bit and remainder before looping. 441 upper = pos; 442 sticky = 0; 443 remainder = 0; 444 rescale_target = 1; 445 scale -= 1; 446 continue; 447 } 448 } 449 break; 450 } 451 } 452 453 Some(scale as u32) 454 } 455 } 456