Path: blob/trunk/third_party/closure/goog/crypt/basen.js
2868 views
// Copyright 2007 The Closure Library Authors. All Rights Reserved.1//2// Licensed under the Apache License, Version 2.0 (the "License");3// you may not use this file except in compliance with the License.4// You may obtain a copy of the License at5//6// http://www.apache.org/licenses/LICENSE-2.07//8// Unless required by applicable law or agreed to in writing, software9// distributed under the License is distributed on an "AS-IS" BASIS,10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.11// See the License for the specific language governing permissions and12// limitations under the License.1314/**15* @fileoverview Numeric base conversion library. Works for arbitrary bases and16* arbitrary length numbers.17*18* For base-64 conversion use base64.js because it is optimized for the specific19* conversion to base-64 while this module is generic. Base-64 is defined here20* mostly for demonstration purpose.21*22* TODO: Make base64 and baseN classes that have common interface. (Perhaps...)23*24*/2526goog.provide('goog.crypt.baseN');272829/**30* Base-2, i.e. '01'.31* @type {string}32*/33goog.crypt.baseN.BASE_BINARY = '01';343536/**37* Base-8, i.e. '01234567'.38* @type {string}39*/40goog.crypt.baseN.BASE_OCTAL = '01234567';414243/**44* Base-10, i.e. '0123456789'.45* @type {string}46*/47goog.crypt.baseN.BASE_DECIMAL = '0123456789';484950/**51* Base-16 using lower case, i.e. '0123456789abcdef'.52* @type {string}53*/54goog.crypt.baseN.BASE_LOWERCASE_HEXADECIMAL = '0123456789abcdef';555657/**58* Base-16 using upper case, i.e. '0123456789ABCDEF'.59* @type {string}60*/61goog.crypt.baseN.BASE_UPPERCASE_HEXADECIMAL = '0123456789ABCDEF';626364/**65* The more-known version of the BASE-64 encoding. Uses + and / characters.66* @type {string}67*/68goog.crypt.baseN.BASE_64 =69'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';707172/**73* URL-safe version of the BASE-64 encoding.74* @type {string}75*/76goog.crypt.baseN.BASE_64_URL_SAFE =77'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';787980/**81* Converts a number from one numeric base to another.82*83* The bases are represented as strings, which list allowed digits. Each digit84* should be unique. The bases can either be user defined, or any of85* goog.crypt.baseN.BASE_xxx.86*87* The number is in human-readable format, most significant digit first, and is88* a non-negative integer. Base designators such as $, 0x, d, b or h (at end)89* will be interpreted as digits, so avoid them. Leading zeros will be trimmed.90*91* Note: for huge bases the result may be inaccurate because of overflowing92* 64-bit doubles used by JavaScript for integer calculus. This may happen93* if the product of the number of digits in the input and output bases comes94* close to 10^16, which is VERY unlikely (100M digits in each base), but95* may be possible in the future unicode world. (Unicode 3.2 has less than 100K96* characters. However, it reserves some more, close to 1M.)97*98* @param {string} number The number to convert.99* @param {string} inputBase The numeric base the number is in (all digits).100* @param {string} outputBase Requested numeric base.101* @return {string} The converted number.102*/103goog.crypt.baseN.recodeString = function(number, inputBase, outputBase) {104if (outputBase == '') {105throw Error('Empty output base');106}107108// Check if number is 0 (special case when we don't want to return '').109var isZero = true;110for (var i = 0, n = number.length; i < n; i++) {111if (number.charAt(i) != inputBase.charAt(0)) {112isZero = false;113break;114}115}116if (isZero) {117return outputBase.charAt(0);118}119120var numberDigits = goog.crypt.baseN.stringToArray_(number, inputBase);121122var inputBaseSize = inputBase.length;123var outputBaseSize = outputBase.length;124125// result = 0.126var result = [];127128// For all digits of number, starting with the most significant ...129for (var i = numberDigits.length - 1; i >= 0; i--) {130// result *= number.base.131var carry = 0;132for (var j = 0, n = result.length; j < n; j++) {133var digit = result[j];134// This may overflow for huge bases. See function comment.135digit = digit * inputBaseSize + carry;136if (digit >= outputBaseSize) {137var remainder = digit % outputBaseSize;138carry = (digit - remainder) / outputBaseSize;139digit = remainder;140} else {141carry = 0;142}143result[j] = digit;144}145while (carry) {146var remainder = carry % outputBaseSize;147result.push(remainder);148carry = (carry - remainder) / outputBaseSize;149}150151// result += number[i].152carry = numberDigits[i];153var j = 0;154while (carry) {155if (j >= result.length) {156// Extend result with a leading zero which will be overwritten below.157result.push(0);158}159var digit = result[j];160digit += carry;161if (digit >= outputBaseSize) {162var remainder = digit % outputBaseSize;163carry = (digit - remainder) / outputBaseSize;164digit = remainder;165} else {166carry = 0;167}168result[j] = digit;169j++;170}171}172173return goog.crypt.baseN.arrayToString_(result, outputBase);174};175176177/**178* Converts a string representation of a number to an array of digit values.179*180* More precisely, the digit values are indices into the number base, which181* is represented as a string, which can either be user defined or one of the182* BASE_xxx constants.183*184* Throws an Error if the number contains a digit not found in the base.185*186* @param {string} number The string to convert, most significant digit first.187* @param {string} base Digits in the base.188* @return {!Array<number>} Array of digit values, least significant digit189* first.190* @private191*/192goog.crypt.baseN.stringToArray_ = function(number, base) {193var index = {};194for (var i = 0, n = base.length; i < n; i++) {195index[base.charAt(i)] = i;196}197var result = [];198for (var i = number.length - 1; i >= 0; i--) {199var character = number.charAt(i);200var digit = index[character];201if (typeof digit == 'undefined') {202throw Error(203'Number ' + number + ' contains a character not found in base ' +204base + ', which is ' + character);205}206result.push(digit);207}208return result;209};210211212/**213* Converts an array representation of a number to a string.214*215* More precisely, the elements of the input array are indices into the base,216* which is represented as a string, which can either be user defined or one of217* the BASE_xxx constants.218*219* Throws an Error if the number contains a digit which is outside the range220* 0 ... base.length - 1.221*222* @param {Array<number>} number Array of digit values, least significant223* first.224* @param {string} base Digits in the base.225* @return {string} Number as a string, most significant digit first.226* @private227*/228goog.crypt.baseN.arrayToString_ = function(number, base) {229var n = number.length;230var chars = [];231var baseSize = base.length;232for (var i = n - 1; i >= 0; i--) {233var digit = number[i];234if (digit >= baseSize || digit < 0) {235throw Error('Number ' + number + ' contains an invalid digit: ' + digit);236}237chars.push(base.charAt(digit));238}239return chars.join('');240};241242243