Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/hamming.h
1 /**
2 * Copyright (c) 2015-present, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD+Patents license found in the
6 * LICENSE file in the root directory of this source tree.
7 */
8
9
10 /* Copyright 2004-present Facebook. All Rights Reserved.
11 *
12 * Hamming distances. The binary vector dimensionality should be a multiple
13 * of 64, as the elementary operations operate on words. If you really need
14 * other sizes, just pad with 0s (this is done by function fvecs2bitvecs).
15 *
16 * User-defined type hamdis_t is used for distances because at this time
17 * it is still uncler clear how we will need to balance
18 * - flexibility in vector size (may need 16- or even 8-bit vectors)
19 * - memory usage
20 * - cache-misses when dealing with large volumes of data (fewer bits is better)
21 *
22 * hamdis_t should optimally be compatibe with one of the Torch Storage
23 * (Byte,Short,Long) and therefore should be signed for 2-bytes and 4-bytes.
24 */
25
26 #ifndef FAISS_hamming_h
27 #define FAISS_hamming_h
28
29
30 #include <stdint.h>
31
32 #include "Heap.h"
33
34
35 /* The Hamming distance type should be exportable to Lua Tensor, which
36 excludes most unsigned type */
37 typedef int32_t hamdis_t;
38
39 namespace faiss {
40
41 inline int popcount64(uint64_t x) {
42 return __builtin_popcountl(x);
43 }
44
45
46 /** Compute a set of Hamming distances between na and nb binary vectors
47 *
48 * @param a size na * nbytespercode
49 * @param b size nb * nbytespercode
50 * @param nbytespercode should be multiple of 8
51 * @param dis output distances, size na * nb
52 */
53 void hammings (
54 const uint8_t * a,
55 const uint8_t * b,
56 size_t na, size_t nb,
57 size_t nbytespercode,
58 hamdis_t * dis);
59
60 void bitvec_print (const uint8_t * b, size_t d);
61
62
63 /* Functions for casting vectors of regular types to compact bits.
64 They assume proper allocation done beforehand, meaning that b
65 should be be able to receive as many bits as x may produce. */
66
67 /* Makes an array of bits from the signs of a float array. The length
68 of the output array b is rounded up to byte size (allocate
69 accordingly) */
70 void fvecs2bitvecs (
71 const float * x,
72 uint8_t * b,
73 size_t d,
74 size_t n);
75
76
77 void fvec2bitvec (const float * x, uint8_t * b, size_t d);
78
79
80
81 /** Return the k smallest Hamming distances for a set of binary query vectors
82 * @param a queries, size ha->nh * ncodes
83 * @param b database, size nb * ncodes
84 * @param nb number of database vectors
85 * @param ncodes size of the binary codes (bytes)
86 * @param ordered if != 0: order the results by decreasing distance
87 * (may be bottleneck for k/n > 0.01) */
88 void hammings_knn (
89 int_maxheap_array_t * ha,
90 const uint8_t * a,
91 const uint8_t * b,
92 size_t nb,
93 size_t ncodes,
94 int ordered);
95
96 /* The core function, without initialization and no re-ordering */
97 void hammings_knn_core (
98 int_maxheap_array_t * ha,
99 const uint8_t * a,
100 const uint8_t * b,
101 size_t nb,
102 size_t ncodes);
103
104
105 /* Counting the number of matches or of cross-matches (without returning them)
106 For use with function that assume pre-allocated memory */
107 void hamming_count_thres (
108 const uint8_t * bs1,
109 const uint8_t * bs2,
110 size_t n1,
111 size_t n2,
112 hamdis_t ht,
113 size_t ncodes,
114 size_t * nptr);
115
116 /* Return all Hamming distances/index passing a thres. Pre-allocation of output
117 is required. Use hamming_count_thres to determine the proper size. */
118 size_t match_hamming_thres (
119 const uint8_t * bs1,
120 const uint8_t * bs2,
121 size_t n1,
122 size_t n2,
123 hamdis_t ht,
124 size_t ncodes,
125 long * idx,
126 hamdis_t * dis);
127
128 /* Cross-matching in a set of vectors */
129 void crosshamming_count_thres (
130 const uint8_t * dbs,
131 size_t n,
132 hamdis_t ht,
133 size_t ncodes,
134 size_t * nptr);
135
136
137 /* compute the Hamming distances between two codewords of nwords*64 bits */
138 hamdis_t hamming (
139 const uint64_t * bs1,
140 const uint64_t * bs2,
141 size_t nwords);
142
143
144
145
146 /******************************************************************
147 * The HammingComputer series of classes compares a single code of
148 * size 4 to 32 to incoming codes. They are intended for use as a
149 * template class where it would be inefficient to switch on the code
150 * size in the inner loop. Hopefully the compiler will inline the
151 * hamming() functions and put the a0, a1, ... in registers.
152 ******************************************************************/
153
154
155 struct HammingComputer4 {
156 uint32_t a0;
157
158 HammingComputer4 (const uint8_t *a, int code_size) {
159 assert (code_size == 4);
160 a0 = *(uint32_t *)a;
161 }
162
163 inline int hamming (const uint8_t *b) const {
164 return popcount64 (*(uint32_t *)b ^ a0);
165 }
166
167 };
168
169 struct HammingComputer8 {
170 uint64_t a0;
171
172 HammingComputer8 (const uint8_t *a, int code_size) {
173 assert (code_size == 8);
174 a0 = *(uint64_t *)a;
175 }
176
177 inline int hamming (const uint8_t *b) const {
178 return popcount64 (*(uint64_t *)b ^ a0);
179 }
180
181 };
182
183
184 struct HammingComputer16 {
185 uint64_t a0, a1;
186 HammingComputer16 (const uint8_t *a8, int code_size) {
187 assert (code_size == 16);
188 const uint64_t *a = (uint64_t *)a8;
189 a0 = a[0]; a1 = a[1];
190 }
191
192 inline int hamming (const uint8_t *b8) const {
193 const uint64_t *b = (uint64_t *)b8;
194 return popcount64 (b[0] ^ a0) + popcount64 (b[1] ^ a1);
195 }
196
197 };
198
199 // when applied to an array, 1/2 of the 64-bit accesses are unaligned.
200 // This incurs a penalty of ~10% wrt. fully aligned accesses.
201 struct HammingComputer20 {
202 uint64_t a0, a1;
203 uint32_t a2;
204
205 HammingComputer20 (const uint8_t *a8, int code_size) {
206 assert (code_size == 20);
207 const uint64_t *a = (uint64_t *)a8;
208 a0 = a[0]; a1 = a[1]; a2 = a[2];
209 }
210
211 inline int hamming (const uint8_t *b8) const {
212 const uint64_t *b = (uint64_t *)b8;
213 return popcount64 (b[0] ^ a0) + popcount64 (b[1] ^ a1) +
214 popcount64 (*(uint32_t*)(b + 2) ^ a2);
215 }
216 };
217
218 struct HammingComputer32 {
219 uint64_t a0, a1, a2, a3;
220
221 HammingComputer32 (const uint8_t *a8, int code_size) {
222 assert (code_size == 32);
223 const uint64_t *a = (uint64_t *)a8;
224 a0 = a[0]; a1 = a[1]; a2 = a[2]; a3 = a[3];
225 }
226
227 inline int hamming (const uint8_t *b8) const {
228 const uint64_t *b = (uint64_t *)b8;
229 return popcount64 (b[0] ^ a0) + popcount64 (b[1] ^ a1) +
230 popcount64 (b[2] ^ a2) + popcount64 (b[3] ^ a3);
231 }
232
233 };
234
235 struct HammingComputer64 {
236 uint64_t a0, a1, a2, a3, a4, a5, a6, a7;
237
238 HammingComputer64 (const uint8_t *a8, int code_size) {
239 assert (code_size == 64);
240 const uint64_t *a = (uint64_t *)a8;
241 a0 = a[0]; a1 = a[1]; a2 = a[2]; a3 = a[3];
242 a4 = a[4]; a5 = a[5]; a6 = a[6]; a7 = a[7];
243 }
244
245 inline int hamming (const uint8_t *b8) const {
246 const uint64_t *b = (uint64_t *)b8;
247 return popcount64 (b[0] ^ a0) + popcount64 (b[1] ^ a1) +
248 popcount64 (b[2] ^ a2) + popcount64 (b[3] ^ a3) +
249 popcount64 (b[4] ^ a4) + popcount64 (b[5] ^ a5) +
250 popcount64 (b[6] ^ a6) + popcount64 (b[7] ^ a7);
251 }
252
253 };
254
255 struct HammingComputerDefault {
256 const uint8_t *a;
257 int n;
258
259 HammingComputerDefault (const uint8_t *a8, int code_size) {
260 a = a8;
261 n = code_size;
262 }
263
264 int hamming (const uint8_t *b8) const {
265 int accu = 0;
266 for (int i = 0; i < n; i++)
267 accu += popcount64 (a[i] ^ b8[i]);
268 return accu;
269 }
270
271 };
272
273
274 struct HammingComputerM8 {
275 const uint64_t *a;
276 int n;
277
278 HammingComputerM8 (const uint8_t *a8, int code_size) {
279 assert (code_size % 8 == 0);
280 a = (uint64_t *)a8;
281 n = code_size / 8;
282 }
283
284 int hamming (const uint8_t *b8) const {
285 const uint64_t *b = (uint64_t *)b8;
286 int accu = 0;
287 for (int i = 0; i < n; i++)
288 accu += popcount64 (a[i] ^ b[i]);
289 return accu;
290 }
291
292 };
293
294 // very inefficient...
295 struct HammingComputerM4 {
296 const uint32_t *a;
297 int n;
298
299 HammingComputerM4 (const uint8_t *a4, int code_size) {
300 assert (code_size % 4 == 0);
301 a = (uint32_t *)a4;
302 n = code_size / 4;
303 }
304 int hamming (const uint8_t *b8) const {
305 const uint32_t *b = (uint32_t *)b8;
306 int accu = 0;
307 for (int i = 0; i < n; i++)
308 accu += popcount64 (a[i] ^ b[i]);
309 return accu;
310 }
311
312 };
313
314 /***************************************************************************
315 * Equivalence with a template class when code size is known at compile time
316 **************************************************************************/
317
318 // default template
319 template<int CODE_SIZE>
320 struct HammingComputer: HammingComputerM8 {
321 HammingComputer (const uint8_t *a, int code_size):
322 HammingComputerM8(a, code_size) {}
323 };
324
325 #define SPECIALIZED_HC(CODE_SIZE) \
326 template<> struct HammingComputer<CODE_SIZE>: \
327 HammingComputer ## CODE_SIZE { \
328 HammingComputer (const uint8_t *a): \
329 HammingComputer ## CODE_SIZE(a, CODE_SIZE) {} \
330 }
331
332 SPECIALIZED_HC(4);
333 SPECIALIZED_HC(8);
334 SPECIALIZED_HC(16);
335 SPECIALIZED_HC(20);
336 SPECIALIZED_HC(32);
337 SPECIALIZED_HC(64);
338
339 #undef SPECIALIZED_HC
340
341
342 /***************************************************************************
343 * generalized Hamming = number of bytes that are different between
344 * two codes.
345 ***************************************************************************/
346
347
348 inline int generalized_hamming_64 (uint64_t a) {
349 a |= a >> 1;
350 a |= a >> 2;
351 a |= a >> 4;
352 a &= 0x0101010101010101UL;
353 return popcount64 (a);
354 }
355
356
357 struct GenHammingComputer8 {
358 uint64_t a0;
359
360 GenHammingComputer8 (const uint8_t *a, int code_size) {
361 assert (code_size == 8);
362 a0 = *(uint64_t *)a;
363 }
364
365 inline int hamming (const uint8_t *b) const {
366 return generalized_hamming_64 (*(uint64_t *)b ^ a0);
367 }
368
369 };
370
371
372 struct GenHammingComputer16 {
373 uint64_t a0, a1;
374 GenHammingComputer16 (const uint8_t *a8, int code_size) {
375 assert (code_size == 16);
376 const uint64_t *a = (uint64_t *)a8;
377 a0 = a[0]; a1 = a[1];
378 }
379
380 inline int hamming (const uint8_t *b8) const {
381 const uint64_t *b = (uint64_t *)b8;
382 return generalized_hamming_64 (b[0] ^ a0) +
383 generalized_hamming_64 (b[1] ^ a1);
384 }
385
386 };
387
388 struct GenHammingComputer32 {
389 uint64_t a0, a1, a2, a3;
390
391 GenHammingComputer32 (const uint8_t *a8, int code_size) {
392 assert (code_size == 32);
393 const uint64_t *a = (uint64_t *)a8;
394 a0 = a[0]; a1 = a[1]; a2 = a[2]; a3 = a[3];
395 }
396
397 inline int hamming (const uint8_t *b8) const {
398 const uint64_t *b = (uint64_t *)b8;
399 return generalized_hamming_64 (b[0] ^ a0) +
400 generalized_hamming_64 (b[1] ^ a1) +
401 generalized_hamming_64 (b[2] ^ a2) +
402 generalized_hamming_64 (b[3] ^ a3);
403 }
404
405 };
406
407 struct GenHammingComputerM8 {
408 const uint64_t *a;
409 int n;
410
411 GenHammingComputerM8 (const uint8_t *a8, int code_size) {
412 assert (code_size % 8 == 0);
413 a = (uint64_t *)a8;
414 n = code_size / 8;
415 }
416
417 int hamming (const uint8_t *b8) const {
418 const uint64_t *b = (uint64_t *)b8;
419 int accu = 0;
420 for (int i = 0; i < n; i++)
421 accu += generalized_hamming_64 (a[i] ^ b[i]);
422 return accu;
423 }
424
425 };
426
427
428 /** generalized Hamming distances (= count number of code bytes that
429 are the same) */
430 void generalized_hammings_knn (
431 int_maxheap_array_t * ha,
432 const uint8_t * a,
433 const uint8_t * b,
434 size_t nb,
435 size_t code_size,
436 int ordered = true);
437
438
439
440
441 } // namespace faiss
442
443
444
445
446 #endif /* FAISS_hamming_h */
faiss::HammingComputerM4
Definition: hamming.h:295
faiss::HammingComputer
Definition: hamming.h:320
faiss::HammingComputer20
Definition: hamming.h:201
faiss::GenHammingComputer16
Definition: hamming.h:372
faiss::GenHammingComputer8
Definition: hamming.h:357
faiss::HammingComputer8
Definition: hamming.h:169
faiss::HammingComputer64
Definition: hamming.h:235
faiss::generalized_hammings_knn
void generalized_hammings_knn(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t code_size, int ordered)
Definition: hamming.cpp:639
faiss::HammingComputer16
Definition: hamming.h:184
faiss::HammingComputer4
Definition: hamming.h:155
faiss::GenHammingComputerM8
Definition: hamming.h:407
faiss::HeapArray
Definition: Heap.h:350
faiss::hammings_knn
void hammings_knn(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t ncodes, int order)
Definition: hamming.cpp:474
faiss::HammingComputer32
Definition: hamming.h:218
faiss::GenHammingComputer32
Definition: hamming.h:388
faiss::HammingComputerDefault
Definition: hamming.h:255
faiss::HammingComputerM8
Definition: hamming.h:274