src/vs/base/common/hash.ts
324 LOC · 249 covered · 75 uncovered · 53 ranges · 11566 concepts · 8 introducers · 5913 tests
File neighbourhood
The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.
Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file
In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.
Graph controls are ready.
Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.
1
>
/*---------------------------------------------------------------------------------------------
hash.ts ×17
2
>
* Copyright (c) Microsoft Corporation. All rights reserved.
3
>
* Licensed under the MIT License. See License.txt in the project root for license information.
4
>
*--------------------------------------------------------------------------------------------*/
5
>
6
>
import { encodeHex, VSBuffer } from './buffer.js';
7
>
import * as strings from './strings.js';
8
>
9
>
type NotSyncHashable = ArrayBufferLike | ArrayBufferView;
10
>
11
>
/**
12
>
* Return a hash value for an object.
13
>
*
14
>
* Note that this should not be used for binary data types. Instead,
15
>
* prefer {@link hashAsync}.
16
>
*/
17
>
export function hash<T>(obj: T extends NotSyncHashable ? never : T): number {
19
>
}
21
>
export function doHash(obj: unknown, hashVal: number): number {
23
>
case 'object':
25
return numberHash(349, hashVal);
27
>
return arrayHash(obj, hashVal);
28
>
}
29
>
return objectHash(obj, hashVal);
31
>
return stringHash(obj, hashVal);
32
>
case 'boolean':
39
return numberHash(617, hashVal);
41
>
}
43
>
export function numberHash(val: number, initialHashVal: number): number {
44
>
return (((initialHashVal << 5) - initialHashVal) + val) | 0; // hashVal * 31 + ch, keep as int32
hash.ts ×2
45
>
}
48
>
return numberHash(b ? 433 : 863, initialHashVal);
49
>
}
51
>
export function stringHash(s: string, hashVal: number) {
53
>
for (let i = 0, length = s.length; i < length; i++) {
54
>
hashVal = numberHash(s.charCodeAt(i), hashVal);
55
>
}
56
>
return hashVal;
57
>
}
60
>
initialHashVal = numberHash(104579, initialHashVal);
61
>
return arr.reduce<number>((hashVal, item) => doHash(item, hashVal), initialHashVal);
62
>
}
65
>
initialHashVal = numberHash(181387, initialHashVal);
66
>
return Object.keys(obj).sort().reduce((hashVal, key) => {
67
>
hashVal = stringHash(key, hashVal);
68
>
return doHash((obj as Record<string, unknown>)[key], hashVal);
69
>
}, initialHashVal);
70
>
}
72
>
73
>
74
>
/** Hashes the input as SHA-1, returning a hex-encoded string. */
75
>
export const hashAsync = (input: string | ArrayBufferView | VSBuffer) => {
76
// Note: I would very much like to expose a streaming interface for hashing
77
// generally, but this is not available in web crypto yet, see
78
// https://github.com/w3c/webcrypto/issues/73
79
80
// StringSHA1 is faster for small string input, use it since we have it:
81
if (typeof input === 'string' && input.length < 250) {
82
const sha = new StringSHA1();
83
sha.update(input);
84
return Promise.resolve(sha.digest());
85
}
86
87
let buff: ArrayBufferView;
88
if (typeof input === 'string') {
89
buff = new TextEncoder().encode(input);
90
} else if (input instanceof VSBuffer) {
91
buff = input.buffer;
92
} else {
93
buff = input;
94
}
95
96
return crypto.subtle.digest('sha-1', buff as ArrayBufferView<ArrayBuffer>).then(toHexString); // CodeQL [SM04514] we use sha1 here for validating old stored client state, not for security
97
};
99
>
const enum SHA1Constant {
100
>
BLOCK_SIZE = 64, // 512 / 8
101
>
UNICODE_REPLACEMENT = 0xFFFD,
102
>
}
103
>
104
>
function leftRotate(value: number, bits: number, totalBits: number = 32): number {
hash.ts ×18
105
>
// delta + bits = totalBits
106
>
const delta = totalBits - bits;
107
>
108
>
// All ones, expect `delta` zeros aligned to the right
109
>
const mask = ~((1 << delta) - 1);
110
>
111
>
// Join (value left-shifted `bits` bits) with (masked value right-shifted `delta` bits)
112
>
return ((value << bits) | ((mask & value) >>> delta)) >>> 0;
113
>
}
115
>
function toHexString(buffer: ArrayBuffer): string;
116
>
function toHexString(value: number, bitsize?: number): string;
117
>
function toHexString(bufferOrValue: ArrayBuffer | number, bitsize: number = 32): string {
hash.ts ×18
118
>
if (bufferOrValue instanceof ArrayBuffer) {
119
return encodeHex(VSBuffer.wrap(new Uint8Array(bufferOrValue)));
120
}
122
>
return (bufferOrValue >>> 0).toString(16).padStart(bitsize / 4, '0');
123
>
}
125
>
/**
126
>
* A SHA1 implementation that works with strings and does not allocate.
127
>
*
128
>
* Prefer to use {@link hashAsync} in async contexts
129
>
*/
130
>
export class StringSHA1 {
131
>
private static _bigBlock32 = new DataView(new ArrayBuffer(320)); // 80 * 4 = 320
132
>
133
>
private _h0 = 0x67452301;
134
>
private _h1 = 0xEFCDAB89;
135
>
private _h2 = 0x98BADCFE;
136
>
private _h3 = 0x10325476;
137
>
private _h4 = 0xC3D2E1F0;
138
>
139
>
private readonly _buff: Uint8Array;
140
>
private readonly _buffDV: DataView;
141
>
private _buffLen: number;
142
>
private _totalLen: number;
143
>
private _leftoverHighSurrogate: number;
144
>
private _finished: boolean;
145
>
146
>
constructor() {
148
>
this._buffDV = new DataView(this._buff.buffer);
149
>
this._buffLen = 0;
150
>
this._totalLen = 0;
151
>
this._leftoverHighSurrogate = 0;
152
>
this._finished = false;
153
>
}
155
>
public update(str: string): void {
157
>
if (strLen === 0) {
158
return;
159
}
161
>
const buff = this._buff;
162
>
let buffLen = this._buffLen;
163
>
let leftoverHighSurrogate = this._leftoverHighSurrogate;
164
>
let charCode: number;
165
>
let offset: number;
166
>
167
>
if (leftoverHighSurrogate !== 0) {
168
charCode = leftoverHighSurrogate;
169
offset = -1;
170
leftoverHighSurrogate = 0;
172
>
charCode = str.charCodeAt(0);
173
>
offset = 0;
174
>
}
175
>
176
>
while (true) {
177
>
let codePoint = charCode;
178
>
if (strings.isHighSurrogate(charCode)) {
179
if (offset + 1 < strLen) {
180
const nextCharCode = str.charCodeAt(offset + 1);
181
if (strings.isLowSurrogate(nextCharCode)) {
182
offset++;
183
codePoint = strings.computeCodePoint(charCode, nextCharCode);
184
} else {
185
// illegal => unicode replacement character
186
codePoint = SHA1Constant.UNICODE_REPLACEMENT;
187
}
188
} else {
189
// last character is a surrogate pair
190
leftoverHighSurrogate = charCode;
191
break;
192
}
194
// illegal => unicode replacement character
195
codePoint = SHA1Constant.UNICODE_REPLACEMENT;
196
}
198
>
buffLen = this._push(buff, buffLen, codePoint);
199
>
offset++;
200
>
if (offset < strLen) {
203
>
break;
204
>
}
205
>
}
206
>
207
>
this._buffLen = buffLen;
208
>
this._leftoverHighSurrogate = leftoverHighSurrogate;
209
>
}
211
>
private _push(buff: Uint8Array, buffLen: number, codePoint: number): number {
213
>
buff[buffLen++] = codePoint;
214
>
} else if (codePoint < 0x0800) {
215
buff[buffLen++] = 0b11000000 | ((codePoint & 0b00000000000000000000011111000000) >>> 6);
216
buff[buffLen++] = 0b10000000 | ((codePoint & 0b00000000000000000000000000111111) >>> 0);
217
} else if (codePoint < 0x10000) {
218
buff[buffLen++] = 0b11100000 | ((codePoint & 0b00000000000000001111000000000000) >>> 12);
219
buff[buffLen++] = 0b10000000 | ((codePoint & 0b00000000000000000000111111000000) >>> 6);
220
buff[buffLen++] = 0b10000000 | ((codePoint & 0b00000000000000000000000000111111) >>> 0);
221
} else {
222
buff[buffLen++] = 0b11110000 | ((codePoint & 0b00000000000111000000000000000000) >>> 18);
223
buff[buffLen++] = 0b10000000 | ((codePoint & 0b00000000000000111111000000000000) >>> 12);
224
buff[buffLen++] = 0b10000000 | ((codePoint & 0b00000000000000000000111111000000) >>> 6);
225
buff[buffLen++] = 0b10000000 | ((codePoint & 0b00000000000000000000000000111111) >>> 0);
226
}
228
>
if (buffLen >= SHA1Constant.BLOCK_SIZE) {
229
this._step();
230
buffLen -= SHA1Constant.BLOCK_SIZE;
231
this._totalLen += SHA1Constant.BLOCK_SIZE;
232
// take last 3 in case of UTF8 overflow
233
buff[0] = buff[SHA1Constant.BLOCK_SIZE + 0];
234
buff[1] = buff[SHA1Constant.BLOCK_SIZE + 1];
235
buff[2] = buff[SHA1Constant.BLOCK_SIZE + 2];
236
}
238
>
return buffLen;
239
>
}
241
>
public digest(): string {
243
>
this._finished = true;
244
>
if (this._leftoverHighSurrogate) {
245
// illegal => unicode replacement character
246
this._leftoverHighSurrogate = 0;
247
this._buffLen = this._push(this._buff, this._buffLen, SHA1Constant.UNICODE_REPLACEMENT);
248
}
250
>
this._wrapUp();
251
>
}
252
>
253
>
return toHexString(this._h0) + toHexString(this._h1) + toHexString(this._h2) + toHexString(this._h3) + toHexString(this._h4);
254
>
}
256
>
private _wrapUp(): void {
258
>
this._buff.subarray(this._buffLen).fill(0);
259
>
260
>
if (this._buffLen > 56) {
261
this._step();
262
this._buff.fill(0);
263
}
265
>
// this will fit because the mantissa can cover up to 52 bits
266
>
const ml = 8 * this._totalLen;
267
>
268
>
this._buffDV.setUint32(56, Math.floor(ml / 4294967296), false);
269
>
this._buffDV.setUint32(60, ml % 4294967296, false);
270
>
271
>
this._step();
272
>
}
274
>
private _step(): void {
276
>
const data = this._buffDV;
277
>
278
>
for (let j = 0; j < 64 /* 16*4 */; j += 4) {
279
>
bigBlock32.setUint32(j, data.getUint32(j, false), false);
280
>
}
281
>
282
>
for (let j = 64; j < 320 /* 80*4 */; j += 4) {
283
>
bigBlock32.setUint32(j, leftRotate((bigBlock32.getUint32(j - 12, false) ^ bigBlock32.getUint32(j - 32, false) ^ bigBlock32.getUint32(j - 56, false) ^ bigBlock32.getUint32(j - 64, false)), 1), false);
284
>
}
285
>
286
>
let a = this._h0;
287
>
let b = this._h1;
288
>
let c = this._h2;
289
>
let d = this._h3;
290
>
let e = this._h4;
291
>
292
>
let f: number, k: number;
293
>
let temp: number;
294
>
295
>
for (let j = 0; j < 80; j++) {
296
>
if (j < 20) {
297
>
f = (b & c) | ((~b) & d);
298
>
k = 0x5A827999;
299
>
} else if (j < 40) {
300
>
f = b ^ c ^ d;
301
>
k = 0x6ED9EBA1;
302
>
} else if (j < 60) {
303
>
f = (b & c) | (b & d) | (c & d);
304
>
k = 0x8F1BBCDC;
305
>
} else {
306
>
f = b ^ c ^ d;
307
>
k = 0xCA62C1D6;
308
>
}
309
>
310
>
temp = (leftRotate(a, 5) + f + e + k + bigBlock32.getUint32(j * 4, false)) & 0xffffffff;
311
>
e = d;
312
>
d = c;
313
>
c = leftRotate(b, 30);
314
>
b = a;
315
>
a = temp;
316
>
}
317
>
318
>
this._h0 = (this._h0 + a) & 0xffffffff;
319
>
this._h1 = (this._h1 + b) & 0xffffffff;
320
>
this._h2 = (this._h2 + c) & 0xffffffff;
321
>
this._h3 = (this._h3 + d) & 0xffffffff;
322
>
this._h4 = (this._h4 + e) & 0xffffffff;
323
>
}