main.js (4467B)
1 /** 2 * @license Apache-2.0 3 * 4 * Copyright (c) 2018 The Stdlib Authors. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 'use strict'; 20 21 // VARIABLES // 22 23 // Define a mask for the least significant 16 bits (low word): 65535 => 0x0000ffff => 00000000000000001111111111111111 24 var LOW_WORD_MASK = 0x0000ffff>>>0; // asm type annotation 25 26 27 // MAIN // 28 29 /** 30 * Performs C-like multiplication of two unsigned 32-bit integers. 31 * 32 * ## Method 33 * 34 * - To emulate C-like multiplication without the aid of 64-bit integers, we recognize that a 32-bit integer can be split into two 16-bit words 35 * 36 * ```tex 37 * a = w_h*2^{16} + w_l 38 * ``` 39 * 40 * where \\( w_h \\) is the most significant 16 bits and \\( w_l \\) is the least significant 16 bits. For example, consider the maximum unsigned 32-bit integer \\( 2^{32}-1 \\) 41 * 42 * ```binarystring 43 * 11111111111111111111111111111111 44 * ``` 45 * 46 * The 16-bit high word is then 47 * 48 * ```binarystring 49 * 1111111111111111 50 * ``` 51 * 52 * and the 16-bit low word 53 * 54 * ```binarystring 55 * 1111111111111111 56 * ``` 57 * 58 * If we cast the high word to 32-bit precision and multiply by \\( 2^{16} \\) (equivalent to a 16-bit left shift), then the bit sequence is 59 * 60 * ```binarystring 61 * 11111111111111110000000000000000 62 * ``` 63 * 64 * Similarly, upon casting the low word to 32-bit precision, the bit sequence is 65 * 66 * ```binarystring 67 * 00000000000000001111111111111111 68 * ``` 69 * 70 * From the rules of binary addition, we recognize that adding the two 32-bit values for the high and low words will return our original value \\( 2^{32}-1 \\). 71 * 72 * - Accordingly, the multiplication of two 32-bit integers can be expressed 73 * 74 * ```tex 75 * \begin{align*} 76 * a \cdot b &= ( a_h \cdot 2^{16} + a_l) \cdot ( b_h \cdot 2^{16} + b_l) \\ 77 * &= a_l \cdot b_l + a_h \cdot b_l \cdot 2^{16} + a_l \cdot b_h \cdot 2^{16} + (a_h \cdot b_h) \cdot 2^{32} \\ 78 * &= a_l \cdot b_l + (a_h \cdot b_l + a_l \cdot b_h) \cdot 2^{16} + (a_h \cdot b_h) \cdot 2^{32} 79 * \end{align*} 80 * ``` 81 * 82 * - We note that multiplying (dividing) an integer by \\( 2^n \\) is equivalent to performing a left (right) shift of \\( n \\) bits. 83 * 84 * - Further, as we want to return an integer of the same precision, for a 32-bit integer, the return value will be modulo \\( 2^{32} \\). Stated another way, we only care about the low word of a 64-bit result. 85 * 86 * - Accordingly, the last term, being evenly divisible by \\( 2^{32} \\), drops from the equation leaving the remaining two terms as the remainder. 87 * 88 * ```tex 89 * a \cdot b = a_l \cdot b_l + (a_h \cdot b_l + a_l \cdot b_h) << 16 90 * ``` 91 * 92 * - Lastly, the second term in the above equation contributes to the middle bits and may cause the product to "overflow". However, we can disregard (`>>>0`) overflow bits due modulo arithmetic, as discussed earlier with regard to the term involving the partial product of high words. 93 * 94 * 95 * @param {uinteger32} a - integer 96 * @param {uinteger32} b - integer 97 * @returns {uinteger32} product 98 * 99 * @example 100 * var v = uimul( 10>>>0, 4>>>0 ); 101 * // returns 40 102 */ 103 function uimul( a, b ) { 104 var lbits; 105 var mbits; 106 var ha; 107 var hb; 108 var la; 109 var lb; 110 111 a >>>= 0; // asm type annotation 112 b >>>= 0; // asm type annotation 113 114 // Isolate the most significant 16-bits: 115 ha = ( a>>>16 )>>>0; // asm type annotation 116 hb = ( b>>>16 )>>>0; // asm type annotation 117 118 // Isolate the least significant 16-bits: 119 la = ( a&LOW_WORD_MASK )>>>0; // asm type annotation 120 lb = ( b&LOW_WORD_MASK )>>>0; // asm type annotation 121 122 // Compute partial sums: 123 lbits = ( la*lb )>>>0; // asm type annotation; no integer overflow possible 124 mbits = ( ((ha*lb) + (la*hb))<<16 )>>>0; // asm type annotation; possible integer overflow 125 126 // The final `>>>0` converts the intermediate sum to an unsigned integer (possible integer overflow during sum): 127 return ( lbits + mbits )>>>0; // asm type annotation 128 } 129 130 131 // EXPORTS // 132 133 module.exports = uimul;