Debian Codegraph @

closure-library/closure/goog/crypt/basen.js

raw
1 // Copyright 2007 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Numeric base conversion library. Works for arbitrary bases and
17 * arbitrary length numbers.
18 *
19 * For base-64 conversion use base64.js because it is optimized for the specific
20 * conversion to base-64 while this module is generic. Base-64 is defined here
21 * mostly for demonstration purpose.
22 *
23 * TODO: Make base64 and baseN classes that have common interface. (Perhaps...)
24 *
25 */
26
27 goog.provide('goog.crypt.baseN');
28
29
30 /**
31 * Base-2, i.e. '01'.
32 * @type {string}
33 */
34 goog.crypt.baseN.BASE_BINARY = '01';
35
36
37 /**
38 * Base-8, i.e. '01234567'.
39 * @type {string}
40 */
41 goog.crypt.baseN.BASE_OCTAL = '01234567';
42
43
44 /**
45 * Base-10, i.e. '0123456789'.
46 * @type {string}
47 */
48 goog.crypt.baseN.BASE_DECIMAL = '0123456789';
49
50
51 /**
52 * Base-16 using lower case, i.e. '0123456789abcdef'.
53 * @type {string}
54 */
55 goog.crypt.baseN.BASE_LOWERCASE_HEXADECIMAL = '0123456789abcdef';
56
57
58 /**
59 * Base-16 using upper case, i.e. '0123456789ABCDEF'.
60 * @type {string}
61 */
62 goog.crypt.baseN.BASE_UPPERCASE_HEXADECIMAL = '0123456789ABCDEF';
63
64
65 /**
66 * The more-known version of the BASE-64 encoding. Uses + and / characters.
67 * @type {string}
68 */
69 goog.crypt.baseN.BASE_64 =
70 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
71
72
73 /**
74 * URL-safe version of the BASE-64 encoding.
75 * @type {string}
76 */
77 goog.crypt.baseN.BASE_64_URL_SAFE =
78 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
79
80
81 /**
82 * Converts a number from one numeric base to another.
83 *
84 * The bases are represented as strings, which list allowed digits. Each digit
85 * should be unique. The bases can either be user defined, or any of
86 * goog.crypt.baseN.BASE_xxx.
87 *
88 * The number is in human-readable format, most significant digit first, and is
89 * a non-negative integer. Base designators such as $, 0x, d, b or h (at end)
90 * will be interpreted as digits, so avoid them. Leading zeros will be trimmed.
91 *
92 * Note: for huge bases the result may be inaccurate because of overflowing
93 * 64-bit doubles used by JavaScript for integer calculus. This may happen
94 * if the product of the number of digits in the input and output bases comes
95 * close to 10^16, which is VERY unlikely (100M digits in each base), but
96 * may be possible in the future unicode world. (Unicode 3.2 has less than 100K
97 * characters. However, it reserves some more, close to 1M.)
98 *
99 * @param {string} number The number to convert.
100 * @param {string} inputBase The numeric base the number is in (all digits).
101 * @param {string} outputBase Requested numeric base.
102 * @return {string} The converted number.
103 */
104 goog.crypt.baseN.recodeString = function(number, inputBase, outputBase) {
105 if (outputBase == '') {
106 throw new Error('Empty output base');
107 }
108
109 // Check if number is 0 (special case when we don't want to return '').
110 var isZero = true;
111 for (var i = 0, n = number.length; i < n; i++) {
112 if (number.charAt(i) != inputBase.charAt(0)) {
113 isZero = false;
114 break;
115 }
116 }
117 if (isZero) {
118 return outputBase.charAt(0);
119 }
120
121 var numberDigits = goog.crypt.baseN.stringToArray_(number, inputBase);
122
123 var inputBaseSize = inputBase.length;
124 var outputBaseSize = outputBase.length;
125
126 // result = 0.
127 var result = [];
128
129 // For all digits of number, starting with the most significant ...
130 for (var i = numberDigits.length - 1; i >= 0; i--) {
131 // result *= number.base.
132 var carry = 0;
133 for (var j = 0, n = result.length; j < n; j++) {
134 var digit = result[j];
135 // This may overflow for huge bases. See function comment.
136 digit = digit * inputBaseSize + carry;
137 if (digit >= outputBaseSize) {
138 var remainder = digit % outputBaseSize;
139 carry = (digit - remainder) / outputBaseSize;
140 digit = remainder;
141 } else {
142 carry = 0;
143 }
144 result[j] = digit;
145 }
146 while (carry) {
147 var remainder = carry % outputBaseSize;
148 result.push(remainder);
149 carry = (carry - remainder) / outputBaseSize;
150 }
151
152 // result += number[i].
153 carry = numberDigits[i];
154 var j = 0;
155 while (carry) {
156 if (j >= result.length) {
157 // Extend result with a leading zero which will be overwritten below.
158 result.push(0);
159 }
160 var digit = result[j];
161 digit += carry;
162 if (digit >= outputBaseSize) {
163 var remainder = digit % outputBaseSize;
164 carry = (digit - remainder) / outputBaseSize;
165 digit = remainder;
166 } else {
167 carry = 0;
168 }
169 result[j] = digit;
170 j++;
171 }
172 }
173
174 return goog.crypt.baseN.arrayToString_(result, outputBase);
175 };
176
177
178 /**
179 * Converts a string representation of a number to an array of digit values.
180 *
181 * More precisely, the digit values are indices into the number base, which
182 * is represented as a string, which can either be user defined or one of the
183 * BASE_xxx constants.
184 *
185 * Throws an Error if the number contains a digit not found in the base.
186 *
187 * @param {string} number The string to convert, most significant digit first.
188 * @param {string} base Digits in the base.
189 * @return {!Array<number>} Array of digit values, least significant digit
190 * first.
191 * @private
192 */
193 goog.crypt.baseN.stringToArray_ = function(number, base) {
194 var index = {};
195 for (var i = 0, n = base.length; i < n; i++) {
196 index[base.charAt(i)] = i;
197 }
198 var result = [];
199 for (var i = number.length - 1; i >= 0; i--) {
200 var character = number.charAt(i);
201 var digit = index[character];
202 if (typeof digit == 'undefined') {
203 throw new Error(
204 'Number ' + number + ' contains a character not found in base ' +
205 base + ', which is ' + character);
206 }
207 result.push(digit);
208 }
209 return result;
210 };
211
212
213 /**
214 * Converts an array representation of a number to a string.
215 *
216 * More precisely, the elements of the input array are indices into the base,
217 * which is represented as a string, which can either be user defined or one of
218 * the BASE_xxx constants.
219 *
220 * Throws an Error if the number contains a digit which is outside the range
221 * 0 ... base.length - 1.
222 *
223 * @param {Array<number>} number Array of digit values, least significant
224 * first.
225 * @param {string} base Digits in the base.
226 * @return {string} Number as a string, most significant digit first.
227 * @private
228 */
229 goog.crypt.baseN.arrayToString_ = function(number, base) {
230 var n = number.length;
231 var chars = [];
232 var baseSize = base.length;
233 for (var i = n - 1; i >= 0; i--) {
234 var digit = number[i];
235 if (digit >= baseSize || digit < 0) {
236 throw new Error(
237 'Number ' + number + ' contains an invalid digit: ' + digit);
238 }
239 chars.push(base.charAt(digit));
240 }
241 return chars.join('');
242 };