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