0
# Bit Array Utilities
1

2
SJCL uses bit arrays (arrays of 32-bit integers) as its internal data representation for all cryptographic operations. The bit array utilities provide essential functions for manipulating, combining, and analyzing these data structures.
3

4
## Capabilities
5

6
### Basic Operations
7

8
Fundamental operations for working with bit arrays.
9

10
```javascript { .api }
11
/**
12
 * Slice bit array in units of bits
13
 * @param {BitArray} a - Source bit array
14
 * @param {number} bstart - Starting bit position
15
 * @param {number} [bend] - Ending bit position (exclusive)
16
 * @returns {BitArray} Sliced bit array
17
 */
18
sjcl.bitArray.bitSlice(a, bstart, bend);
19

20
/**
21
 * Extract a number from bit array
22
 * @param {BitArray} a - Source bit array
23
 * @param {number} bstart - Starting bit position
24
 * @param {number} blength - Number of bits to extract
25
 * @returns {number} Extracted value as integer
26
 */
27
sjcl.bitArray.extract(a, bstart, blength);
28

29
/**
30
 * Concatenate two bit arrays
31
 * @param {BitArray} a1 - First bit array
32
 * @param {BitArray} a2 - Second bit array
33
 * @returns {BitArray} Concatenated bit array
34
 */
35
sjcl.bitArray.concat(a1, a2);
36
```
37

38
**Usage Examples:**
39

40
```javascript
41
const sjcl = require('sjcl');
42

43
// Create test bit arrays
44
const array1 = sjcl.codec.hex.toBits('deadbeef');
45
const array2 = sjcl.codec.hex.toBits('cafebabe');
46

47
console.log('Array 1:', sjcl.codec.hex.fromBits(array1));
48
console.log('Array 2:', sjcl.codec.hex.fromBits(array2));
49

50
// Concatenate arrays
51
const combined = sjcl.bitArray.concat(array1, array2);
52
console.log('Combined:', sjcl.codec.hex.fromBits(combined)); // "deadbeefcafebabe"
53

54
// Slice bit array
55
const slice = sjcl.bitArray.bitSlice(combined, 16, 48); // Extract middle 32 bits
56
console.log('Slice:', sjcl.codec.hex.fromBits(slice));
57

58
// Extract specific bits
59
const extracted = sjcl.bitArray.extract(array1, 8, 8); // Extract bits 8-15
60
console.log('Extracted byte:', extracted.toString(16));
61
```
62

63
### Length and Size Operations
64

65
Determine and manipulate bit array lengths.
66

67
```javascript { .api }
68
/**
69
 * Find length of bit array in bits
70
 * @param {BitArray} a - Bit array to measure
71
 * @returns {number} Length in bits
72
 */
73
sjcl.bitArray.bitLength(a);
74

75
/**
76
 * Truncate bit array to specified bit length
77
 * @param {BitArray} a - Source bit array
78
 * @param {number} len - Desired length in bits
79
 * @returns {BitArray} Truncated bit array
80
 */
81
sjcl.bitArray.clamp(a, len);
82
```
83

84
**Usage Examples:**
85

86
```javascript
87
const sjcl = require('sjcl');
88

89
// Create bit array from hex
90
const data = sjcl.codec.hex.toBits('deadbeefcafebabe');
91
console.log('Original length:', sjcl.bitArray.bitLength(data)); // 64 bits
92

93
// Clamp to different sizes
94
const clamped32 = sjcl.bitArray.clamp(data, 32);
95
console.log('Clamped to 32 bits:', sjcl.codec.hex.fromBits(clamped32)); // "deadbeef"
96

97
const clamped24 = sjcl.bitArray.clamp(data, 24);
98
console.log('Clamped to 24 bits:', sjcl.codec.hex.fromBits(clamped24)); // "deadbe"
99

100
// Extend with clamp (pads with zeros)
101
const extended = sjcl.bitArray.clamp(data, 96);
102
console.log('Extended to 96 bits:', sjcl.codec.hex.fromBits(extended));
103
console.log('Extended length:', sjcl.bitArray.bitLength(extended));
104
```
105

106
### Partial Word Operations
107

108
Handle partial 32-bit words for precise bit manipulation.
109

110
```javascript { .api }
111
/**
112
 * Make partial word for bit array
113
 * @param {number} len - Number of bits used (1-32)
114
 * @param {number} x - Word value
115
 * @param {number} [_end] - Endianness flag
116
 * @returns {number} Partial word with length encoding
117
 */
118
sjcl.bitArray.partial(len, x, _end);
119

120
/**
121
 * Get number of bits used by partial word
122
 * @param {number} x - Partial word
123
 * @returns {number} Number of bits used (1-32, or 32 if full word)
124
 */
125
sjcl.bitArray.getPartial(x);
126
```
127

128
**Usage Examples:**
129

130
```javascript
131
const sjcl = require('sjcl');
132

133
// Create partial words
134
const partial8 = sjcl.bitArray.partial(8, 0xAB); // 8-bit partial word
135
const partial16 = sjcl.bitArray.partial(16, 0xCDEF); // 16-bit partial word
136

137
console.log('8-bit partial length:', sjcl.bitArray.getPartial(partial8)); // 8
138
console.log('16-bit partial length:', sjcl.bitArray.getPartial(partial16)); // 16
139

140
// Build array with partial word
141
const arrayWithPartial = [0xDEADBEEF, partial8];
142
console.log('Array length:', sjcl.bitArray.bitLength(arrayWithPartial)); // 40 bits
143

144
// Convert to hex to see the result
145
console.log('Hex:', sjcl.codec.hex.fromBits(arrayWithPartial));
146
```
147

148
### Comparison Operations
149

150
Secure comparison functions for cryptographic applications.
151

152
```javascript { .api }
153
/**
154
 * Compare two bit arrays for equality in constant time
155
 * @param {BitArray} a - First bit array
156
 * @param {BitArray} b - Second bit array
157
 * @returns {boolean} True if arrays are equal
158
 */
159
sjcl.bitArray.equal(a, b);
160
```
161

162
**Usage Examples:**
163

164
```javascript
165
const sjcl = require('sjcl');
166

167
// Create identical arrays
168
const array1 = sjcl.codec.hex.toBits('deadbeef');
169
const array2 = sjcl.codec.hex.toBits('deadbeef');
170
const array3 = sjcl.codec.hex.toBits('cafebabe');
171

172
// Constant-time comparison (secure against timing attacks)
173
console.log('Arrays 1 and 2 equal:', sjcl.bitArray.equal(array1, array2)); // true
174
console.log('Arrays 1 and 3 equal:', sjcl.bitArray.equal(array1, array3)); // false
175

176
// Use in cryptographic verification
177
function verifyMAC(message, key, providedMAC) {
178
  const hmac = new sjcl.misc.hmac(key);
179
  const computedMAC = hmac.encrypt(message);
180
  
181
  // Secure comparison prevents timing attacks
182
  return sjcl.bitArray.equal(computedMAC, providedMAC);
183
}
184

185
// Example usage
186
const key = sjcl.random.randomWords(8);
187
const message = "Important message";
188
const hmac = new sjcl.misc.hmac(key);
189
const mac = hmac.encrypt(message);
190

191
const isValid = verifyMAC(message, key, mac);
192
console.log('MAC verification:', isValid);
193
```
194

195
### Binary Operations
196

197
Low-level binary operations on bit arrays.
198

199
```javascript { .api }
200
/**
201
 * XOR two 4-word bit arrays
202
 * @param {BitArray} a - First 4-word array
203
 * @param {BitArray} b - Second 4-word array
204
 * @returns {BitArray} XOR result as 4-word array
205
 */
206
sjcl.bitArray.i(a, b);
207

208
/**
209
 * Byteswap word array in place
210
 * @param {BitArray} a - Bit array to byteswap
211
 * @returns {BitArray} Same array (modified in place)
212
 */
213
sjcl.bitArray.byteswapM(a);
214
```
215

216
**Usage Examples:**
217

218
```javascript
219
const sjcl = require('sjcl');
220

221
// XOR operation (works on 4-word arrays)
222
const a = sjcl.codec.hex.toBits('deadbeefcafebabe12345678');
223
const b = sjcl.codec.hex.toBits('1234567890abcdef87654321');
224

225
// Ensure both are exactly 4 words
226
const a4 = sjcl.bitArray.clamp(a, 128);
227
const b4 = sjcl.bitArray.clamp(b, 128);
228

229
const xorResult = sjcl.bitArray.i(a4, b4);
230
console.log('XOR result:', sjcl.codec.hex.fromBits(xorResult));
231

232
// Byteswap example
233
const original = sjcl.codec.hex.toBits('deadbeef');
234
console.log('Original:', sjcl.codec.hex.fromBits(original));
235

236
const swapped = sjcl.bitArray.byteswapM(original.slice()); // Clone first
237
console.log('Byteswapped:', sjcl.codec.hex.fromBits(swapped));
238
```
239

240
## Advanced Operations
241

242
### Bit Shifting and Rotation
243

244
Implement bit shifting operations using SJCL's internal functions:
245

246
```javascript
247
const sjcl = require('sjcl');
248

249
// Left shift implementation
250
function leftShift(bits, positions) {
251
  const result = [];
252
  let carry = 0;
253
  
254
  for (let i = bits.length - 1; i >= 0; i--) {
255
    const word = bits[i];
256
    result[i] = ((word << positions) | carry) >>> 0;
257
    carry = word >>> (32 - positions);
258
  }
259
  
260
  if (carry !== 0) {
261
    result.unshift(carry);
262
  }
263
  
264
  return result;
265
}
266

267
// Right shift implementation
268
function rightShift(bits, positions) {
269
  const result = [];
270
  let carry = 0;
271
  
272
  for (let i = 0; i < bits.length; i++) {
273
    const word = bits[i];
274
    result[i] = (word >>> positions) | carry;
275
    carry = (word << (32 - positions)) >>> 0;
276
  }
277
  
278
  return result;
279
}
280

281
// Usage
282
const data = sjcl.codec.hex.toBits('deadbeef');
283
console.log('Original:', sjcl.codec.hex.fromBits(data));
284

285
const shifted = leftShift(data, 4);
286
console.log('Left shifted by 4:', sjcl.codec.hex.fromBits(shifted));
287

288
const rightShifted = rightShift(data, 4);
289
console.log('Right shifted by 4:', sjcl.codec.hex.fromBits(rightShifted));
290
```
291

292
### Custom Bit Manipulation
293

294
Implement custom bit manipulation functions:
295

296
```javascript
297
const sjcl = require('sjcl');
298

299
class BitArrayUtil {
300
  // Set specific bit to 1
301
  static setBit(bits, position) {
302
    const wordIndex = Math.floor(position / 32);
303
    const bitIndex = position % 32;
304
    const result = bits.slice(); // Clone array
305
    
306
    if (wordIndex < result.length) {
307
      result[wordIndex] |= (1 << (31 - bitIndex));
308
    }
309
    
310
    return result;
311
  }
312
  
313
  // Clear specific bit to 0
314
  static clearBit(bits, position) {
315
    const wordIndex = Math.floor(position / 32);
316
    const bitIndex = position % 32;
317
    const result = bits.slice();
318
    
319
    if (wordIndex < result.length) {
320
      result[wordIndex] &= ~(1 << (31 - bitIndex));
321
    }
322
    
323
    return result;
324
  }
325
  
326
  // Test if specific bit is set
327
  static testBit(bits, position) {
328
    const wordIndex = Math.floor(position / 32);
329
    const bitIndex = position % 32;
330
    
331
    if (wordIndex >= bits.length) return false;
332
    
333
    return (bits[wordIndex] & (1 << (31 - bitIndex))) !== 0;
334
  }
335
  
336
  // Count number of set bits (Hamming weight)
337
  static popCount(bits) {
338
    let count = 0;
339
    
340
    for (const word of bits) {
341
      // Brian Kernighan's algorithm
342
      let w = word >>> 0; // Ensure unsigned
343
      while (w) {
344
        w &= w - 1;
345
        count++;
346
      }
347
    }
348
    
349
    return count;
350
  }
351
  
352
  // Reverse bits in array
353
  static reverse(bits) {
354
    const result = [];
355
    const totalBits = sjcl.bitArray.bitLength(bits);
356
    
357
    for (let i = 0; i < totalBits; i++) {
358
      const sourceBit = totalBits - 1 - i;
359
      if (BitArrayUtil.testBit(bits, sourceBit)) {
360
        result = BitArrayUtil.setBit(result, i);
361
      } else {
362
        result = BitArrayUtil.clearBit(result, i);
363
      }
364
    }
365
    
366
    return sjcl.bitArray.clamp(result, totalBits);
367
  }
368
}
369

370
// Usage examples
371
const data = sjcl.codec.hex.toBits('f0f0f0f0');
372
console.log('Original:', sjcl.codec.hex.fromBits(data));
373

374
// Set bit 4
375
const withBitSet = BitArrayUtil.setBit(data, 4);
376
console.log('Bit 4 set:', sjcl.codec.hex.fromBits(withBitSet));
377

378
// Test bits
379
console.log('Bit 0 set:', BitArrayUtil.testBit(data, 0)); // true (f starts with 1111)
380
console.log('Bit 4 set:', BitArrayUtil.testBit(data, 4)); // false (0 in f0f0)
381

382
// Count set bits
383
console.log('Set bits:', BitArrayUtil.popCount(data));
384
```
385

386
### Data Validation
387

388
Validate bit array integrity and format:
389

390
```javascript
391
const sjcl = require('sjcl');
392

393
class BitArrayValidator {
394
  // Check if array is valid bit array
395
  static isValid(bits) {
396
    if (!Array.isArray(bits)) return false;
397
    
398
    for (let i = 0; i < bits.length; i++) {
399
      const word = bits[i];
400
      
401
      // Check if it's a number
402
      if (typeof word !== 'number') return false;
403
      
404
      // Check if it's a valid 32-bit integer
405
      if (!Number.isInteger(word)) return false;
406
      
407
      // Check if it's in valid range
408
      if (word < 0 || word > 0xFFFFFFFF) return false;
409
      
410
      // Check partial word (last word might have length encoding)
411
      if (i === bits.length - 1) {
412
        const partialBits = sjcl.bitArray.getPartial(word);
413
        if (partialBits < 1 || partialBits > 32) return false;
414
      }
415
    }
416
    
417
    return true;
418
  }
419
  
420
  // Sanitize bit array
421
  static sanitize(bits) {
422
    if (!Array.isArray(bits)) return [];
423
    
424
    return bits.filter(word => {
425
      return typeof word === 'number' && 
426
             Number.isInteger(word) && 
427
             word >= 0 && 
428
             word <= 0xFFFFFFFF;
429
    });
430
  }
431
  
432
  // Get array statistics
433
  static getStats(bits) {
434
    return {
435
      isValid: BitArrayValidator.isValid(bits),
436
      wordCount: bits.length,
437
      bitLength: sjcl.bitArray.bitLength(bits),
438
      byteLength: Math.ceil(sjcl.bitArray.bitLength(bits) / 8),
439
      isEmpty: bits.length === 0,
440
      hasPartialWord: bits.length > 0 && sjcl.bitArray.getPartial(bits[bits.length - 1]) !== 32
441
    };
442
  }
443
}
444

445
// Usage
446
const testData = sjcl.codec.hex.toBits('deadbeef');
447
const stats = BitArrayValidator.getStats(testData);
448
console.log('Array stats:', stats);
449

450
// Test invalid data
451
const invalidData = [0xDEADBEEF, -1, 'invalid', 0x100000000];
452
console.log('Invalid data valid:', BitArrayValidator.isValid(invalidData)); // false
453

454
const sanitized = BitArrayValidator.sanitize(invalidData);
455
console.log('Sanitized:', sanitized); // [0xDEADBEEF]
456
```
457

458
## Performance Considerations
459

460
1. **Memory Usage**: Each 32-bit word uses 8 bytes in JavaScript
461
2. **Cloning**: Use `.slice()` to clone arrays before modification
462
3. **Length Checks**: Cache bit lengths for repeated operations
463
4. **Partial Words**: Minimize partial word operations for better performance
464
5. **Native Operations**: Use built-in methods when possible
465

466
## Security Considerations
467

468
1. **Timing Attacks**: Use `sjcl.bitArray.equal()` for secure comparisons
469
2. **Memory Clearing**: JavaScript can't securely clear memory
470
3. **Constant Time**: Most bit operations are NOT constant-time
471
4. **Data Validation**: Always validate input bit arrays
472
5. **Side Channels**: Be aware of potential information leakage
473

474
## Common Patterns
475

476
1. **Data Conversion**: Convert between formats via bit arrays
477
2. **Padding**: Use `clamp()` to pad or truncate data
478
3. **Chunking**: Use `bitSlice()` to process data in chunks
479
4. **Verification**: Use `equal()` for cryptographic comparisons
480
5. **Concatenation**: Use `concat()` to build composite data structures