Coverage Report

Created: 2021-04-14 15:26

/home/liu/buildslave/linux-x64-runtests/build/lib/ccv_util.c
Line
Count
Source (jump to first uncovered line)
1
#include "ccv.h"
2
#include "ccv_internal.h"
3
4
ccv_dense_matrix_t* ccv_get_dense_matrix(ccv_matrix_t* mat)
5
297k
{
6
297k
  int type = *(int*)mat;
7
297k
  if (type & CCV_MATRIX_DENSE)
8
298k
    return (ccv_dense_matrix_t*)mat;
9
18.4E
  return 0;
10
18.4E
}
11
12
ccv_sparse_matrix_t* ccv_get_sparse_matrix(ccv_matrix_t* mat)
13
0
{
14
0
  int type = *(int*)mat;
15
0
  if (type & CCV_MATRIX_SPARSE)
16
0
    return (ccv_sparse_matrix_t*)mat;
17
0
  return 0;
18
0
}
19
20
void ccv_visualize(ccv_matrix_t* a, ccv_matrix_t** b, int type)
21
0
{
22
0
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
23
0
  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_literal("ccv_visualize"), da->sig, CCV_EOF_SIGN);
24
0
  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_8U | CCV_C1, CCV_8U | CCV_C1, sig);
25
0
  ccv_object_return_if_cached(, db);
26
0
  ccv_dense_matrix_t* dc = 0;
27
0
  if (CCV_GET_CHANNEL(da->type) > CCV_C1)
28
0
  {
29
0
    ccv_flatten(da, (ccv_matrix_t**)&dc, 0, 0);
30
0
    da = dc;
31
0
  }
32
0
  int i, j;
33
0
  double minval = DBL_MAX, maxval = -DBL_MAX;
34
0
  unsigned char* aptr = da->data.u8;
35
0
  unsigned char* bptr = db->data.u8;
36
0
#define for_block(_, _for_get) \
37
0
  for (i = 0; i < da->rows; i++) \
38
0
  { \
39
0
    for (j = 0; j < da->cols; j++) \
40
0
    { \
41
0
      minval = ccv_min(minval, _for_get(aptr, j)); \
42
0
      maxval = ccv_max(maxval, _for_get(aptr, j)); \
43
0
    } \
44
0
    aptr += da->step; \
45
0
  } \
46
0
  aptr = da->data.u8; \
47
0
  for (i = 0; i < da->rows; i++) \
48
0
  { \
49
0
    for (j = 0; j < da->cols; j++) \
50
0
      bptr[j] = ccv_clamp((_for_get(aptr, j) - minval) * 255.0 / (maxval - minval), 0, 255); \
51
0
    aptr += da->step; \
52
0
    bptr += db->step; \
53
0
  }
54
0
  ccv_matrix_getter(da->type, for_block);
55
0
#undef for_block
56
0
  if (dc != 0)
57
0
    ccv_matrix_free(dc);
58
0
}
59
60
void ccv_zero(ccv_matrix_t* mat)
61
209
{
62
209
  ccv_dense_matrix_t* dmt = ccv_get_dense_matrix(mat);
63
209
  memset(dmt->data.u8, 0, dmt->step * dmt->rows);
64
209
}
65
66
int ccv_any_nan(ccv_matrix_t *a)
67
141k
{
68
141k
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
69
141k
  assert((da->type & CCV_32F) || (da->type & CCV_64F));
70
141k
  int ch = CCV_GET_CHANNEL(da->type);
71
141k
  int i;
72
141k
  if (da->type & CCV_32F)
73
141k
  {
74
113M
    for (i = 0; i < da->rows * da->cols * ch; 
i++113M
)
75
#ifdef isnanf
76
      if (isnanf(da->data.f32[i]))
77
#else
78
113M
      if (isnan(da->data.f32[i]))
79
113M
#endif
80
113M
        
return i + 10
;
81
18.4E
  } else {
82
18.4E
    for (i = 0; i < da->rows * da->cols * ch; 
i++0
)
83
0
      if (isnan(da->data.f64[i]))
84
0
        return i + 1;
85
18.4E
  }
86
141k
  return 0;
87
141k
}
88
89
void ccv_flatten(ccv_matrix_t* a, ccv_matrix_t** b, int type, int flag)
90
1
{
91
1
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
92
1
  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_flatten(%d)", flag), da->sig, CCV_EOF_SIGN);
93
1
  int no_8u_type = (da->type & CCV_8U) ? CCV_32S : 
da->type0
;
94
1
  type = (type == 0) ? CCV_GET_DATA_TYPE(no_8u_type) | CCV_C1 : 
CCV_GET_DATA_TYPE0
(type) | CCV_C10
;
95
1
  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_ALL_DATA_TYPE | CCV_C1, type, sig);
96
1
  ccv_object_return_if_cached(, db);
97
1
  int i, j, k, ch = CCV_GET_CHANNEL(da->type);
98
1
  unsigned char* aptr = da->data.u8;
99
1
  unsigned char* bptr = db->data.u8;
100
1
#define for_block(_for_get, _for_type, _for_set) \
101
3
  
for (i = 0; 1
i < da->rows;
i++2
) \
102
2
  { \
103
6
    for (j = 0; j < da->cols; 
j++4
) \
104
4
    { \
105
4
      _for_type sum = 0; \
106
12
      for (k = 0; k < ch; 
k++8
) \
107
8
        sum += 
_for_get4
(aptr, j * ch + k); \
108
4
      _for_set(bptr, j, sum); \
109
4
    } \
110
2
    aptr += da->step; \
111
2
    bptr += db->step; \
112
2
  }
113
1
  ccv_matrix_getter(da->type, ccv_matrix_typeof_setter, db->type, for_block);
114
1
#undef for_block
115
1
}
116
117
void ccv_border(ccv_matrix_t* a, ccv_matrix_t** b, int type, ccv_margin_t margin)
118
1
{
119
1
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
120
1
  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_border(%d,%d,%d,%d)", margin.left, margin.top, margin.right, margin.bottom), da->sig, CCV_EOF_SIGN);
121
1
  int ch = CCV_GET_CHANNEL(da->type);
122
1
  type = (type == 0) ? CCV_GET_DATA_TYPE(da->type) | ch : 
CCV_GET_DATA_TYPE0
(type) | ch0
;
123
1
  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows + margin.top + margin.bottom, da->cols + margin.left + margin.right, CCV_ALL_DATA_TYPE | ch, type, sig);
124
1
  ccv_object_return_if_cached(, db);
125
1
  ccv_zero(db);
126
1
  int i, j;
127
1
  unsigned char* aptr = da->data.u8;
128
1
  unsigned char* bptr = db->data.u8 + margin.top * db->step + margin.left * ch * CCV_GET_DATA_TYPE_SIZE(db->type);
129
1
  if (CCV_GET_DATA_TYPE(da->type) == CCV_GET_DATA_TYPE(db->type))
130
1
  {
131
1
    // use memcpy to speedup
132
1
    size_t scan = da->cols * ch * CCV_GET_DATA_TYPE_SIZE(da->type);
133
2
    for (i = 0; i < da->rows; 
i++1
)
134
1
    {
135
1
      memcpy(bptr, aptr, scan);
136
1
      aptr += da->step;
137
1
      bptr += db->step;
138
1
    }
139
1
  } else {
140
0
#define for_block(_for_get, _for_type, _for_set) \
141
0
    for (i = 0; i < da->rows; i++) \
142
0
    { \
143
0
      for (j = 0; j < da->cols * ch; j++) \
144
0
      { \
145
0
        _for_set(bptr, j, _for_get(aptr, j)); \
146
0
      } \
147
0
      aptr += da->step; \
148
0
      bptr += db->step; \
149
0
    }
150
0
    ccv_matrix_getter(da->type, ccv_matrix_typeof_setter, db->type, for_block);
151
0
#undef for_block
152
0
  }
153
1
}
154
155
void ccv_shift(ccv_matrix_t* a, ccv_matrix_t** b, int type, int lr, int rr)
156
10
{
157
10
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
158
10
  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_shift(%d,%d)", lr, rr), da->sig, CCV_EOF_SIGN);
159
10
  type = (type == 0) ? 
CCV_GET_DATA_TYPE0
(da->type) | 0
CCV_GET_CHANNEL0
(da->type) : CCV_GET_DATA_TYPE(type) | CCV_GET_CHANNEL(da->type);
160
10
  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_ALL_DATA_TYPE | CCV_GET_CHANNEL(da->type), type, sig); 
161
10
  ccv_object_return_if_cached(, db);
162
10
  int i, j, ch = CCV_GET_CHANNEL(da->type);
163
10
  unsigned char* aptr = da->data.u8;
164
10
  unsigned char* bptr = db->data.u8;
165
10
#define for_block(_for_get, _for_set) \
166
5.21k
  
for (i = 0; 10
i < da->rows;
i++5.20k
) \
167
5.20k
  { \
168
8.88M
    for (j = 0; j < da->cols * ch; 
j++8.88M
) \
169
8.88M
    { \
170
8.88M
      _for_set(bptr, j, _for_get(aptr, j, lr), rr); \
171
8.88M
    } \
172
5.20k
    aptr += da->step; \
173
5.20k
    bptr += db->step; \
174
5.20k
  }
175
10
  ccv_matrix_getter(da->type, ccv_matrix_setter, db->type, for_block);
176
10
#undef for_block
177
10
}
178
179
// From https://github.com/skarupke/flat_hash_map with anything overflows 32bit removed.
180
static uint32_t _ccv_sparse_matrix_index_for_hash(const uint32_t hash, const int prime_index)
181
210M
{
182
210M
  switch(prime_index)
183
210M
  {
184
0
  case 0:
185
0
    return 0u;
186
697k
  case 1:
187
697k
    return hash % 2u;
188
0
  case 2:
189
0
    return hash % 3u;
190
865k
  case 3:
191
865k
    return hash % 5u;
192
0
  case 4:
193
0
    return hash % 7u;
194
782k
  case 5:
195
782k
    return hash % 11u;
196
0
  case 6:
197
0
    return hash % 13u;
198
0
  case 7:
199
0
    return hash % 17u;
200
423k
  case 8:
201
423k
    return hash % 23u;
202
0
  case 9:
203
0
    return hash % 29u;
204
0
  case 10:
205
0
    return hash % 37u;
206
759k
  case 11:
207
759k
    return hash % 47u;
208
0
  case 12:
209
0
    return hash % 59u;
210
0
  case 13:
211
0
    return hash % 73u;
212
1.00M
  case 14:
213
1.00M
    return hash % 97u;
214
0
  case 15:
215
0
    return hash % 127u;
216
0
  case 16:
217
0
    return hash % 151u;
218
947k
  case 17:
219
947k
    return hash % 197u;
220
0
  case 18:
221
0
    return hash % 251u;
222
0
  case 19:
223
0
    return hash % 313u;
224
1.32M
  case 20:
225
1.32M
    return hash % 397u;
226
0
  case 21:
227
0
    return hash % 499u;
228
0
  case 22:
229
0
    return hash % 631u;
230
2.80M
  case 23:
231
2.80M
    return hash % 797u;
232
0
  case 24:
233
0
    return hash % 1009u;
234
0
  case 25:
235
0
    return hash % 1259u;
236
201M
  case 26:
237
201M
    return hash % 1597u;
238
0
  case 27:
239
0
    return hash % 2011u;
240
0
  case 28:
241
0
    return hash % 2539u;
242
0
  case 29:
243
0
    return hash % 3203u;
244
0
  case 30:
245
0
    return hash % 4027u;
246
0
  case 31:
247
0
    return hash % 5087u;
248
0
  case 32:
249
0
    return hash % 6421u;
250
0
  case 33:
251
0
    return hash % 8089u;
252
0
  case 34:
253
0
    return hash % 10193u;
254
0
  case 35:
255
0
    return hash % 12853u;
256
0
  case 36:
257
0
    return hash % 16193u;
258
0
  case 37:
259
0
    return hash % 20399u;
260
0
  case 38:
261
0
    return hash % 25717u;
262
0
  case 39:
263
0
    return hash % 32401u;
264
0
  case 40:
265
0
    return hash % 40823u;
266
0
  case 41:
267
0
    return hash % 51437u;
268
0
  case 42:
269
0
    return hash % 64811u;
270
0
  case 43:
271
0
    return hash % 81649u;
272
0
  case 44:
273
0
    return hash % 102877u;
274
0
  case 45:
275
0
    return hash % 129607u;
276
0
  case 46:
277
0
    return hash % 163307u;
278
0
  case 47:
279
0
    return hash % 205759u;
280
0
  case 48:
281
0
    return hash % 259229u;
282
0
  case 49:
283
0
    return hash % 326617u;
284
0
  case 50:
285
0
    return hash % 411527u;
286
0
  case 51:
287
0
    return hash % 518509u;
288
0
  case 52:
289
0
    return hash % 653267u;
290
0
  case 53:
291
0
    return hash % 823117u;
292
0
  case 54:
293
0
    return hash % 1037059u;
294
0
  case 55:
295
0
    return hash % 1306601u;
296
0
  case 56:
297
0
    return hash % 1646237u;
298
0
  case 57:
299
0
    return hash % 2074129u;
300
0
  case 58:
301
0
    return hash % 2613229u;
302
0
  case 59:
303
0
    return hash % 3292489u;
304
0
  case 60:
305
0
    return hash % 4148279u;
306
0
  case 61:
307
0
    return hash % 5226491u;
308
0
  case 62:
309
0
    return hash % 6584983u;
310
0
  case 63:
311
0
    return hash % 8296553u;
312
0
  case 64:
313
0
    return hash % 10453007u;
314
0
  case 65:
315
0
    return hash % 13169977u;
316
0
  case 66:
317
0
    return hash % 16593127u;
318
0
  case 67:
319
0
    return hash % 20906033u;
320
0
  case 68:
321
0
    return hash % 26339969u;
322
0
  case 69:
323
0
    return hash % 33186281u;
324
0
  case 70:
325
0
    return hash % 41812097u;
326
0
  case 71:
327
0
    return hash % 52679969u;
328
0
  case 72:
329
0
    return hash % 66372617u;
330
0
  case 73:
331
0
    return hash % 83624237u;
332
0
  case 74:
333
0
    return hash % 105359939u;
334
0
  case 75:
335
0
    return hash % 132745199u;
336
0
  case 76:
337
0
    return hash % 167248483u;
338
0
  case 77:
339
0
    return hash % 210719881u;
340
0
  case 78:
341
0
    return hash % 265490441u;
342
0
  case 79:
343
0
    return hash % 334496971u;
344
0
  case 80:
345
0
    return hash % 421439783u;
346
0
  case 81:
347
0
    return hash % 530980861u;
348
0
  case 82:
349
0
    return hash % 668993977u;
350
0
  case 83:
351
0
    return hash % 842879579u;
352
0
  case 84:
353
0
    return hash % 1061961721u;
354
0
  case 85:
355
0
    return hash % 1337987929u;
356
0
  case 86:
357
0
    return hash % 1685759167u;
358
0
  case 87:
359
0
    return hash % 2123923447u;
360
0
  case 88:
361
0
    return hash % 2675975881u;
362
0
  case 89:
363
0
    return hash % 3371518343u;
364
0
  case 90:
365
0
    return hash % 4247846927u;
366
0
  case 91:
367
0
    return hash % 4294967291u;
368
0
  default:
369
0
    return hash;
370
210M
  }
371
210M
}
372
373
// prime numbers generated by the following method:
374
// 1. start with a prime p = 2
375
// 2. go to wolfram alpha and get p = NextPrime(2 * p)
376
// 3. repeat 2. until you overflow 32 bits
377
// you now have large gaps which you would hit if somebody called reserve() with an unlucky number.
378
// 4. to fill the gaps for every prime p go to wolfram alpha and get ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in the gaps
379
// 5. get PrevPrime(2^32) and put it at the end
380
const static uint32_t _ccv_sparse_prime[] =
381
{
382
  2u, 3u, 5u, 7u, 11u, 13u, 17u, 23u, 29u, 37u, 47u,
383
  59u, 73u, 97u, 127u, 151u, 197u, 251u, 313u, 397u,
384
  499u, 631u, 797u, 1009u, 1259u, 1597u, 2011u, 2539u,
385
  3203u, 4027u, 5087u, 6421u, 8089u, 10193u, 12853u, 16193u,
386
  20399u, 25717u, 32401u, 40823u, 51437u, 64811u, 81649u,
387
  102877u, 129607u, 163307u, 205759u, 259229u, 326617u,
388
  411527u, 518509u, 653267u, 823117u, 1037059u, 1306601u,
389
  1646237u, 2074129u, 2613229u, 3292489u, 4148279u, 5226491u,
390
  6584983u, 8296553u, 10453007u, 13169977u, 16593127u, 20906033u,
391
  26339969u, 33186281u, 41812097u, 52679969u, 66372617u,
392
  83624237u, 105359939u, 132745199u, 167248483u, 210719881u,
393
  265490441u, 334496971u, 421439783u, 530980861u, 668993977u,
394
  842879579u, 1061961721u, 1337987929u, 1685759167u, 2123923447u,
395
  2675975881u, 3371518343u, 4247846927u, 4294967291u
396
};
397
398
static uint8_t _ccv_sparse_matrix_index_next_size_over(const uint32_t size)
399
131k
{
400
131k
  int i;
401
131k
  assert(sizeof(_ccv_sparse_prime) / sizeof(uint32_t) == 91);
402
700k
  
for (i = 0; 131k
i < sizeof(_ccv_sparse_prime) / sizeof(uint32_t);
i++568k
)
403
700k
    if (_ccv_sparse_prime[i] > size)
404
131k
      return i + 1;
405
131k
  
return sizeof(_ccv_sparse_prime) / sizeof(uint32_t) + 10
;
406
131k
}
407
408
static uint32_t _ccv_sparse_matrix_size_for_index(const int prime_index)
409
131k
{
410
131k
  return _ccv_sparse_prime[prime_index - 1];
411
131k
}
412
413
static void _ccv_init_sparse_matrix_vector(ccv_sparse_matrix_vector_t* vector, const ccv_sparse_matrix_t* const mat)
414
98.4k
{
415
98.4k
  if (mat->type & CCV_DENSE_VECTOR)
416
183
  {
417
183
    const int vlen = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
mat->rows0
: mat->cols;
418
183
    const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);
419
183
    vector->size = vlen;
420
183
    vector->data.u8 = (uint8_t*)cccalloc(1, (cell_size * vlen + 15) & -16);
421
183
    return;
422
183
  }
423
98.2k
  vector->prime_index = 1; // See ccv_util.c to know why this is 1 and why size is 2.
424
98.2k
  vector->size = 2;
425
98.2k
  vector->rnum = 0;
426
98.2k
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
427
98.2k
  vector->index = (ccv_sparse_matrix_index_t*)cccalloc(sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned, vector->size);
428
98.2k
}
429
430
static inline void _ccv_move_sparse_matrix_vector(ccv_sparse_matrix_index_t* const index, ccv_sparse_matrix_vector_t* const vector, const ccv_sparse_matrix_t* const mat, uint32_t k, uint32_t idx, int i, const uint32_t size, const int prime_index)
431
5.26k
{
432
5.26k
  uint32_t old_i = index[idx].i;
433
5.26k
  index[idx].i = i;
434
5.26k
  i = old_i;
435
5.26k
  ccv_sparse_matrix_vector_t val = vector[idx];
436
5.26k
  _ccv_init_sparse_matrix_vector(vector + idx, mat);
437
5.26k
  // Move to next idx, this is already occupied.
438
5.26k
  ++k;
439
5.26k
  ++idx;
440
102k
  for (; k < 255; 
++idx, ++k96.7k
)
441
102k
  {
442
102k
    if (idx >= size)
443
129
      idx = 0;
444
102k
    if (!index[idx].ifbit)
445
5.26k
    {
446
5.26k
      index[idx].ifbit = k;
447
5.26k
      index[idx].i = i;
448
5.26k
      vector[idx] = val;
449
5.26k
      return;
450
5.26k
    }
451
96.7k
    uint32_t j = index[idx].ifbit;
452
96.7k
    if (k > j)
453
80.7k
    {
454
80.7k
      index[idx].ifbit = k;
455
80.7k
      k = j;
456
80.7k
      uint32_t old_i = index[idx].i;
457
80.7k
      index[idx].i = i;
458
80.7k
      i = old_i;
459
80.7k
      ccv_sparse_matrix_vector_t old_val = vector[idx];
460
80.7k
      vector[idx] = val;
461
80.7k
      val = old_val;
462
80.7k
    }
463
96.7k
  }
464
5.26k
  
for (;; 0
++idx, ++k0
)
465
0
  {
466
0
    if (idx >= size)
467
0
      idx = 0;
468
0
    if (!index[idx].ifbit)
469
0
    {
470
0
      index[idx].ifbit = k > 0xff ? 0xff : k;
471
0
      index[idx].i = i;
472
0
      vector[idx] = val;
473
0
      return;
474
0
    }
475
0
    uint32_t j = index[idx].ifbit;
476
0
    if (j == 0xff)
477
0
      j = _ccv_sparse_matrix_index_for_hash(index[idx].i + size - idx, prime_index) + 2;
478
0
    if (k > j)
479
0
    {
480
0
      index[idx].ifbit = k > 0xff ? 0xff : k;
481
0
      k = j;
482
0
      uint32_t old_i = index[idx].i;
483
0
      index[idx].i = i;
484
0
      i = old_i;
485
0
      ccv_sparse_matrix_vector_t old_val = vector[idx];
486
0
      vector[idx] = val;
487
0
      val = old_val;
488
0
    }
489
0
  }
490
0
}
491
492
static ccv_sparse_matrix_vector_t* _ccv_get_or_add_sparse_matrix_vector(ccv_sparse_matrix_t* mat, int i)
493
1.79M
{
494
1.79M
  const uint32_t size = mat->size;
495
1.79M
  ccv_sparse_matrix_index_t* const index = mat->index;
496
1.79M
  ccv_sparse_matrix_vector_t* const vector = mat->vector;
497
1.79M
  const int prime_index = mat->prime_index;
498
1.79M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(i, prime_index);
499
1.79M
  uint32_t k = 2;
500
3.20M
  for (; k < 255; 
++idx, ++k1.40M
)
501
3.20M
  {
502
3.20M
    if (idx >= size)
503
510
      idx = 0;
504
3.20M
    uint32_t j = index[idx].ifbit;
505
3.20M
    if (k > j)
506
98.4k
    {
507
98.4k
      ++mat->rnum;
508
98.4k
      index[idx].ifbit = k;
509
98.4k
      if (!j)
510
93.1k
      {
511
93.1k
        index[idx].i = i;
512
93.1k
        _ccv_init_sparse_matrix_vector(vector + idx, mat);
513
93.1k
      } else
514
5.26k
        _ccv_move_sparse_matrix_vector(index, vector, mat, j /* This is j not k because we are replacing it. */, idx, i, size, prime_index);
515
98.4k
      return vector + idx;
516
98.4k
    }
517
3.10M
    if (index[idx].i == i)
518
1.70M
      return vector + idx;
519
3.10M
  }
520
1.79M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
521
1.79M
  
for (;; 0
++idx, ++k0
)
522
0
  {
523
0
    if (idx >= size)
524
0
      idx = 0;
525
0
    uint32_t j = index[idx].ifbit;
526
0
    if (j == 0xff)
527
0
      j = _ccv_sparse_matrix_index_for_hash(index[idx].i + size - idx, prime_index) + 2;
528
0
    if (k > j)
529
0
    {
530
0
      ++mat->rnum;
531
0
      index[idx].ifbit = k > 0xff ? 0xff : k;
532
0
      if (!j)
533
0
      {
534
0
        index[idx].i = i;
535
0
        _ccv_init_sparse_matrix_vector(vector + idx, mat);
536
0
      } else
537
0
        _ccv_move_sparse_matrix_vector(index, vector, mat, j /* This is j not k because we are replacing it. */, idx, i, size, prime_index);
538
0
      return vector + idx;
539
0
    }
540
0
    if (index[idx].i == i)
541
0
      return vector + idx;
542
0
  }
543
0
  return 0;
544
0
}
545
546
ccv_sparse_matrix_vector_t* ccv_get_sparse_matrix_vector(const ccv_sparse_matrix_t* mat, int i)
547
102M
{
548
102M
  const uint32_t size = mat->size;
549
102M
  ccv_sparse_matrix_index_t* index = mat->index;
550
102M
  ccv_sparse_matrix_vector_t* vector = mat->vector;
551
102M
  const int prime_index = mat->prime_index;
552
102M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(i, prime_index);
553
102M
  uint32_t k = 2;
554
107M
  for (; k < 255; 
++idx, ++k4.57M
)
555
107M
  {
556
107M
    if (idx >= size)
557
596
      idx = 0;
558
107M
    if (k > index[idx].ifbit)
559
597k
      return 0;
560
106M
    if (index[idx].i == i)
561
102M
      return vector + idx;
562
106M
  }
563
102M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
564
102M
  
for (;; 0
++idx, ++k0
)
565
0
  {
566
0
    if (idx >= size)
567
0
      idx = 0;
568
0
    uint32_t j = index[idx].ifbit;
569
0
    if (j == 0xff)
570
0
      j = _ccv_sparse_matrix_index_for_hash(index[idx].i + size - idx, prime_index) + 2;
571
0
    if (k > j)
572
0
      return 0;
573
0
    if (index[idx].i == i)
574
0
      return vector + idx;
575
0
  }
576
0
  return 0;
577
0
}
578
579
ccv_numeric_data_t ccv_get_sparse_matrix_cell_from_vector(const ccv_sparse_matrix_t* mat, ccv_sparse_matrix_vector_t* vector, int vidx)
580
102M
{
581
102M
  ccv_numeric_data_t cell = {}; // zero-init.
582
102M
  const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);
583
102M
  if (mat->type & CCV_DENSE_VECTOR)
584
0
  {
585
0
    cell.u8 = vector->data.u8 + cell_size * vidx;
586
0
    return cell;
587
0
  }
588
102M
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
589
102M
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
590
102M
  const uint32_t size = vector->size;
591
102M
  uint8_t* const index = (uint8_t*)vector->index;
592
102M
  const int prime_index = vector->prime_index;
593
102M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(vidx, prime_index);
594
102M
  uint32_t k = 2;
595
104M
  for (; k < 255; 
++idx, ++k1.82M
)
596
104M
  {
597
104M
    if (idx >= size)
598
169k
      idx = 0;
599
104M
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
600
104M
    if (k > index_idx->ifbit)
601
1.90M
      return cell;
602
102M
    if (index_idx->i == vidx)
603
100M
    {
604
100M
      cell.u8 = (uint8_t*)(index_idx + 1);
605
100M
      return cell;
606
100M
    }
607
102M
  }
608
102M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
609
102M
  
for (;; 0
++idx, ++k0
)
610
0
  {
611
0
    if (idx >= size)
612
0
      idx = 0;
613
0
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
614
0
    uint32_t j = index_idx->ifbit;
615
0
    if (j == 0xff)
616
0
      j = _ccv_sparse_matrix_index_for_hash(index_idx->i + size - idx, prime_index) + 2;
617
0
    if (k > j)
618
0
      return cell;
619
0
    if (index_idx->i == vidx)
620
0
    {
621
0
      cell.u8 = (uint8_t*)(index_idx + 1);
622
0
      return cell;
623
0
    }
624
0
  }
625
0
}
626
627
ccv_numeric_data_t ccv_get_sparse_matrix_cell(const ccv_sparse_matrix_t* mat, int row, int col)
628
102M
{
629
102M
  ccv_sparse_matrix_vector_t* vector = ccv_get_sparse_matrix_vector(mat, (mat->major == CCV_SPARSE_COL_MAJOR) ? 
col0
: row);
630
102M
  if (!vector || 
!vector->rnum101M
)
631
500k
    return (ccv_numeric_data_t){};
632
101M
  const int vidx = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
row0
: col;
633
101M
  return ccv_get_sparse_matrix_cell_from_vector(mat, vector, vidx);
634
101M
}
635
636
static void _ccv_sparse_matrix_vector_inc_size(const ccv_sparse_matrix_t* const mat, ccv_sparse_matrix_vector_t* const vector)
637
103k
{
638
103k
  assert(vector->prime_index >= 0 && vector->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
639
103k
  const uint32_t size = vector->size;
640
103k
  const int prime_index = vector->prime_index = _ccv_sparse_matrix_index_next_size_over(size * 2);
641
103k
  const uint32_t new_size = vector->size = _ccv_sparse_matrix_size_for_index(vector->prime_index);
642
103k
  assert(vector->prime_index >= 0 && vector->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
643
103k
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
644
103k
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
645
103k
  const size_t cell_rnum = cell_size_aligned / sizeof(uint32_t);
646
103k
  vector->index = (ccv_sparse_matrix_index_t*)ccrealloc(vector->index, index_size * new_size);
647
103k
  uint8_t* const index = (uint8_t*)vector->index;
648
103k
  memset(index + index_size * size, 0, index_size * (new_size - size));
649
103k
  uint32_t i, h;
650
2.46M
  for (i = 0; i < size; 
i++2.36M
)
651
2.36M
  {
652
2.36M
    ccv_sparse_matrix_index_t* index_i = (ccv_sparse_matrix_index_t*)(index + index_size * i);
653
2.36M
    index_i->ifbit = !!index_i->ifbit; // Mark this as need to be moved around.
654
2.36M
  }
655
2.46M
  for (i = 0; i < size; 
i++2.36M
)
656
2.36M
  {
657
2.36M
    ccv_sparse_matrix_index_t* index_i = (ccv_sparse_matrix_index_t*)(index + index_size * i);
658
2.36M
    if (index_i->ifbit == 1) // Encountered one need to be moved.
659
2.00M
    {
660
2.00M
      index_i->ifbit = 0;
661
2.00M
      // This item is from old hash table, need to find a new location for it.
662
2.00M
      uint32_t key = index_i->i;
663
2.00M
      uint32_t* val = (uint32_t*)(index_i + 1);
664
2.00M
      uint32_t k = 2;
665
2.00M
      uint32_t idx = _ccv_sparse_matrix_index_for_hash(key, prime_index);
666
2.32M
      for (; k < 255; 
++idx, ++k319k
)
667
2.32M
      {
668
2.32M
        if (idx >= new_size)
669
998
          idx = 0;
670
2.32M
        ccv_sparse_matrix_index_t* index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
671
2.32M
        uint32_t j = index_idx->ifbit;
672
2.32M
        if (!j)
673
2.00M
        {
674
2.00M
          index_idx->ifbit = k;
675
2.00M
          index_idx->i = key;
676
2.00M
          memcpy(index_idx + 1, val, cell_size_aligned);
677
2.00M
          break;
678
2.00M
        }
679
319k
        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.
680
226k
          continue;
681
93.2k
        index_idx->ifbit = k;
682
93.2k
        uint32_t old_key = index_idx->i;
683
93.2k
        index_idx->i = key;
684
93.2k
        key = old_key;
685
93.2k
        uint32_t* old_val = (uint32_t*)(index_idx + 1);
686
188k
        for (h = 0; h < cell_rnum; 
h++94.8k
)
687
94.8k
        {
688
94.8k
          uint32_t v = old_val[h];
689
94.8k
          old_val[h] = val[h];
690
94.8k
          val[h] = v;
691
94.8k
        }
692
93.2k
        if (j != 1)
693
40.9k
          k = j;
694
52.3k
        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.
695
52.3k
          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;
696
52.3k
          k = 1; // Restart.
697
52.3k
        }
698
93.2k
      }
699
2.00M
      if (k < 255)
700
2.00M
        continue;
701
0
      for (;; ++idx, ++k)
702
0
      {
703
0
        if (idx >= new_size)
704
0
          idx = 0;
705
0
        ccv_sparse_matrix_index_t* index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
706
0
        uint32_t j = index_idx->ifbit;
707
0
        if (!j)
708
0
        {
709
0
          index_idx->ifbit = k > 0xff ? 0xff : k;
710
0
          index_idx->i = key;
711
0
          memcpy(index_idx + 1, val, cell_size_aligned);
712
0
          break;
713
0
        }
714
0
        if (j == 0xff)
715
0
          j = _ccv_sparse_matrix_index_for_hash((index_idx->i + new_size - idx), prime_index) + 2; // This is valid because on overflow, unsigned is well defined.
716
0
        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.
717
0
          continue;
718
0
        index_idx->ifbit = k > 0xff ? 0xff : k;
719
0
        uint32_t old_key = index_idx->i;
720
0
        index_idx->i = key;
721
0
        key = old_key;
722
0
        uint32_t* old_val = (uint32_t*)(index_idx + 1);
723
0
        for (h = 0; h < cell_rnum; h++)
724
0
        {
725
0
          uint32_t v = old_val[h];
726
0
          old_val[h] = val[h];
727
0
          val[h] = v;
728
0
        }
729
0
        if (j != 1)
730
0
          k = j;
731
0
        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.
732
0
          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;
733
0
          k = 1; // Restart.
734
0
        }
735
0
      }
736
0
    }
737
2.36M
  }
738
103k
}
739
740
static void _ccv_sparse_matrix_inc_size(ccv_sparse_matrix_t* mat)
741
28.1k
{
742
28.1k
  assert(mat->prime_index >= 0 && mat->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
743
28.1k
  const uint32_t size = mat->size;
744
28.1k
  const int prime_index = mat->prime_index = _ccv_sparse_matrix_index_next_size_over(size * 2);
745
28.1k
  const uint32_t new_size = mat->size = _ccv_sparse_matrix_size_for_index(mat->prime_index);
746
28.1k
  assert(mat->prime_index >= 0 && mat->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
747
28.1k
  ccv_sparse_matrix_index_t* const index = mat->index = (ccv_sparse_matrix_index_t*)ccrealloc(mat->index, sizeof(ccv_sparse_matrix_index_t) * new_size);
748
28.1k
  memset(index + size, 0, sizeof(ccv_sparse_matrix_index_t) * (new_size - size));
749
28.1k
  ccv_sparse_matrix_vector_t* const vector = mat->vector = (ccv_sparse_matrix_vector_t*)ccrealloc(mat->vector, sizeof(ccv_sparse_matrix_vector_t) * new_size);
750
28.1k
  uint32_t i;
751
139k
  for (i = 0; i < size; 
i++111k
)
752
111k
    index[i].ifbit = !!index[i].ifbit; // Mark this as need to be moved around.
753
139k
  for (i = 0; i < size; 
i++111k
)
754
111k
    if (index[i].ifbit == 1) // Encountered one need to be moved.
755
79.8k
    {
756
79.8k
      index[i].ifbit = 0;
757
79.8k
      // This item is from old hash table, need to find a new location for it.
758
79.8k
      uint32_t key = index[i].i;
759
79.8k
      ccv_sparse_matrix_vector_t val = vector[i];
760
79.8k
      uint32_t k = 2;
761
79.8k
      uint32_t idx = _ccv_sparse_matrix_index_for_hash(key, prime_index);
762
105k
      for (; k < 255; 
++idx, ++k25.5k
)
763
105k
      {
764
105k
        if (idx >= new_size)
765
6
          idx = 0;
766
105k
        uint32_t j = index[idx].ifbit;
767
105k
        if (!j)
768
79.8k
        {
769
79.8k
          index[idx].ifbit = k;
770
79.8k
          index[idx].i = key;
771
79.8k
          vector[idx] = val;
772
79.8k
          break;
773
79.8k
        }
774
25.5k
        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.
775
21.8k
          continue;
776
3.75k
        index[idx].ifbit = k;
777
3.75k
        uint32_t old_key = index[idx].i;
778
3.75k
        index[idx].i = key;
779
3.75k
        key = old_key;
780
3.75k
        ccv_sparse_matrix_vector_t old_val = vector[idx];
781
3.75k
        vector[idx] = val;
782
3.75k
        val = old_val;
783
3.75k
        if (j != 1)
784
2.88k
          k = j;
785
872
        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.
786
872
          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;
787
872
          k = 1; // Restart.
788
872
        }
789
3.75k
      }
790
79.8k
      if (k < 255)
791
79.8k
        continue;
792
0
      for (;; ++idx, ++k)
793
0
      {
794
0
        if (idx >= new_size)
795
0
          idx = 0;
796
0
        uint32_t j = index[idx].ifbit;
797
0
        if (!j)
798
0
        {
799
0
          index[idx].ifbit = k > 0xff ? 0xff : k;
800
0
          index[idx].i = key;
801
0
          vector[idx] = val;
802
0
          break;
803
0
        }
804
0
        if (j == 0xff)
805
0
          j = _ccv_sparse_matrix_index_for_hash((index[idx].i + new_size - idx), prime_index) + 2; // This is valid because on overflow, unsigned is well defined.
806
0
        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.
807
0
          continue;
808
0
        index[idx].ifbit = k > 0xff ? 0xff : k;
809
0
        uint32_t old_key = index[idx].i;
810
0
        index[idx].i = key;
811
0
        key = old_key;
812
0
        ccv_sparse_matrix_vector_t old_val = vector[idx];
813
0
        vector[idx] = val;
814
0
        val = old_val;
815
0
        if (j != 1)
816
0
          k = j;
817
0
        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.
818
0
          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;
819
0
          k = 1; // Restart.
820
0
        }
821
0
      }
822
0
    }
823
28.1k
}
824
825
static inline void _ccv_move_sparse_matrix_cell(uint8_t* const index, uint32_t k, uint32_t idx, int i, const uint32_t size, const int prime_index, const size_t index_size, const size_t cell_size_aligned)
826
87.8k
{
827
87.8k
  ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
828
87.8k
  const size_t cell_rnum = cell_size_aligned / sizeof(uint32_t);
829
87.8k
  uint32_t* val = (uint32_t*)(index_idx + 1);
830
87.8k
  uint32_t old_i = index_idx->i;
831
87.8k
  index_idx->i = i;
832
87.8k
  i = old_i;
833
87.8k
  // Move to next idx, this is already occupied.
834
87.8k
  ++k;
835
87.8k
  ++idx;
836
87.8k
  uint32_t h;
837
1.03M
  for (; k < 255; 
++idx, ++k945k
)
838
1.03M
  {
839
1.03M
    if (idx >= size)
840
5.02k
      idx = 0;
841
1.03M
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
842
1.03M
    if (!index_idx->ifbit)
843
87.8k
    {
844
87.8k
      index_idx->ifbit = k;
845
87.8k
      index_idx->i = i;
846
87.8k
      memcpy(index_idx + 1, val, cell_size_aligned);
847
87.8k
      return;
848
87.8k
    }
849
945k
    uint32_t j = index_idx->ifbit;
850
945k
    if (k > j)
851
854k
    {
852
854k
      index_idx->ifbit = k;
853
854k
      k = j;
854
854k
      uint32_t old_i = index_idx->i;
855
854k
      index_idx->i = i;
856
854k
      i = old_i;
857
854k
      uint32_t* old_val = (uint32_t*)(index_idx + 1);
858
1.73M
      for (h = 0; h < cell_rnum; 
h++880k
)
859
880k
      {
860
880k
        uint32_t v = old_val[h];
861
880k
        old_val[h] = val[h];
862
880k
        val[h] = v;
863
880k
      }
864
854k
    }
865
945k
  }
866
87.8k
  
for (;; 0
++idx, ++k0
)
867
0
  {
868
0
    if (idx >= size)
869
0
      idx = 0;
870
0
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
871
0
    if (!index_idx->ifbit)
872
0
    {
873
0
      index_idx->ifbit = k > 0xff ? 0xff : k;
874
0
      index_idx->i = i;
875
0
      memcpy(index_idx + 1, val, cell_size_aligned);
876
0
      return;
877
0
    }
878
0
    uint32_t j = index_idx->ifbit;
879
0
    if (j == 0xff)
880
0
      j = _ccv_sparse_matrix_index_for_hash(index_idx->i + size - idx, prime_index) + 2;
881
0
    if (k > j)
882
0
    {
883
0
      index_idx->ifbit = k > 0xff ? 0xff : k;
884
0
      k = j;
885
0
      uint32_t old_i = index_idx->i;
886
0
      index_idx->i = i;
887
0
      i = old_i;
888
0
      uint32_t* old_val = (uint32_t*)(index_idx + 1);
889
0
      for (h = 0; h < cell_rnum; h++)
890
0
      {
891
0
        uint32_t v = old_val[h];
892
0
        old_val[h] = val[h];
893
0
        val[h] = v;
894
0
      }
895
0
    }
896
0
  }
897
0
}
898
899
void ccv_set_sparse_matrix_cell(ccv_sparse_matrix_t* mat, int row, int col, const void* data)
900
1.79M
{
901
1.79M
  assert(data);
902
1.79M
  const int hidx = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
col200
:
row1.79M
;
903
1.79M
  const int vidx = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
row200
:
col1.79M
;
904
1.79M
  // This will handle initialize a vector if it doesn't already exist.
905
1.79M
  if ((mat->rnum + 1) * 10llu > mat->size * 9llu) // expand when reached 90%.
906
28.1k
    _ccv_sparse_matrix_inc_size(mat);
907
1.79M
  ccv_sparse_matrix_vector_t* const vector = _ccv_get_or_add_sparse_matrix_vector(mat, hidx);
908
1.79M
  const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);
909
1.79M
  if (mat->type & CCV_DENSE_VECTOR)
910
400
  {
911
400
    memcpy(vector->data.u8 + vidx * cell_size, data, cell_size);
912
400
    return;
913
400
  }
914
1.79M
  if ((vector->rnum + 1) * 10llu > vector->size * 9llu) // expand when reached 90%.
915
103k
    _ccv_sparse_matrix_vector_inc_size(mat, vector);
916
1.79M
  // Align to 4 bytes.
917
1.79M
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
918
1.79M
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
919
1.79M
  uint8_t* const index = (uint8_t*)vector->index;
920
1.79M
  const int prime_index = vector->prime_index;
921
1.79M
  const uint32_t size = vector->size;
922
1.79M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(vidx, prime_index);
923
1.79M
  uint32_t k = 2;
924
2.50M
  for (; k < 255; 
++idx, ++k710k
)
925
2.50M
  {
926
2.50M
    if (idx >= size)
927
7.83k
      idx = 0;
928
2.50M
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
929
2.50M
    uint32_t j = index_idx->ifbit;
930
2.50M
    if (k > j)
931
1.63M
    {
932
1.63M
      ++vector->rnum;
933
1.63M
      index_idx->ifbit = k;
934
1.63M
      if (!j)
935
1.54M
      {
936
1.54M
        index_idx->i = vidx;
937
1.54M
        // Assign it out.
938
1.54M
        memcpy(index_idx + 1, data, cell_size);
939
1.54M
      } else {
940
87.8k
        _ccv_move_sparse_matrix_cell(index, j /* This is j not k because we are replacing it. */, idx, vidx, size, prime_index, index_size, cell_size_aligned);
941
87.8k
        memcpy(index_idx + 1, data, cell_size);
942
87.8k
      }
943
1.63M
      return;
944
1.63M
    }
945
872k
    if (index_idx->i == vidx)
946
161k
    {
947
161k
      memcpy(index_idx + 1, data, cell_size);
948
161k
      return;
949
161k
    }
950
872k
  }
951
1.79M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
952
1.79M
  
for (;; 0
++idx, ++k0
)
953
0
  {
954
0
    if (idx >= size)
955
0
      idx = 0;
956
0
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
957
0
    uint32_t j = index_idx->ifbit;
958
0
    if (j == 0xff)
959
0
      j = _ccv_sparse_matrix_index_for_hash(index_idx->i + size - idx, prime_index) + 2;
960
0
    if (k > j)
961
0
    {
962
0
      ++vector->rnum;
963
0
      index_idx->ifbit = k > 0xff ? 0xff : k;
964
0
      if (!j)
965
0
      {
966
0
        index_idx->i = vidx;
967
0
        memcpy(index_idx + 1, data, cell_size);
968
0
      } else {
969
0
        _ccv_move_sparse_matrix_cell(index, j /* This is j not k because we are replacing it. */, idx, vidx, size, prime_index, index_size, cell_size_aligned);
970
0
        memcpy(index_idx + 1, data, cell_size);
971
0
      }
972
0
      return;
973
0
    }
974
0
    if (index_idx->i == vidx)
975
0
    {
976
0
      memcpy(index_idx + 1, data, cell_size);
977
0
      return;
978
0
    }
979
0
  }
980
0
}
981
982
3
#define _ccv_indice_less_than(i1, i2, aux) ((i1) < (i2))
983
0
#define _ccv_swap_indice_and_uchar_data(i1, i2, array, aux, t) {  \
984
0
  unsigned char td = (aux)[(int)(&(i1) - (array))];       \
985
0
  (aux)[(int)(&(i1) - (array))] = (aux)[(int)(&(i2) - (array))]; \
986
0
  (aux)[(int)(&(i2) - (array))] = td;             \
987
0
  CCV_SWAP(i1, i2, t); }
988
0
#define _ccv_swap_indice_and_int_data(i1, i2, array, aux, t) { \
989
0
  int td = (aux)[(int)(&(i1) - (array))];           \
990
0
  (aux)[(int)(&(i1) - (array))] = (aux)[(int)(&(i2) - (array))]; \
991
0
  (aux)[(int)(&(i2) - (array))] = td;             \
992
0
  CCV_SWAP(i1, i2, t); }
993
0
#define _ccv_swap_indice_and_float_data(i1, i2, array, aux, t) {  \
994
0
  float td = (aux)[(int)(&(i1) - (array))];           \
995
0
  (aux)[(int)(&(i1) - (array))] = (aux)[(int)(&(i2) - (array))]; \
996
0
  (aux)[(int)(&(i2) - (array))] = td;             \
997
0
  CCV_SWAP(i1, i2, t); }
998
0
#define _ccv_swap_indice_and_double_data(i1, i2, array, aux, t) { \
999
0
  double td = (aux)[(int)(&(i1) - (array))];           \
1000
0
  (aux)[(int)(&(i1) - (array))] = (aux)[(int)(&(i2) - (array))]; \
1001
0
  (aux)[(int)(&(i2) - (array))] = td;             \
1002
0
  CCV_SWAP(i1, i2, t); }
1003
1004
0
static CCV_IMPLEMENT_QSORT_EX(_ccv_indice_uchar_sort, int, _ccv_indice_less_than, _ccv_swap_indice_and_uchar_data, unsigned char*);
1005
0
static CCV_IMPLEMENT_QSORT_EX(_ccv_indice_int_sort, int, _ccv_indice_less_than, _ccv_swap_indice_and_int_data, int*);
1006
3
static CCV_IMPLEMENT_QSORT_EX(_ccv_indice_float_sort, int, _ccv_indice_less_than, 
_ccv_swap_indice_and_float_data0
, float*);
1007
0
static CCV_IMPLEMENT_QSORT_EX(_ccv_indice_double_sort, int, _ccv_indice_less_than, _ccv_swap_indice_and_double_data, double*);
1008
1009
void ccv_compress_sparse_matrix(const ccv_sparse_matrix_t* mat, ccv_compressed_sparse_matrix_t** csm)
1010
1
{
1011
1
  uint32_t i, j;
1012
1
  int nnz = 0;
1013
1
  const uint32_t size = mat->size;
1014
6
  for (i = 0; i < size; 
i++5
)
1015
5
  {
1016
5
    ccv_sparse_matrix_index_t* index = mat->index + i;
1017
5
    ccv_sparse_matrix_vector_t* vector = mat->vector + i;
1018
5
    if (index->ifbit <= 1 || 
!vector->rnum3
)
1019
2
      continue;
1020
3
    if (mat->type & CCV_DENSE_VECTOR)
1021
0
    {
1022
0
#define while_block(_, _while_get) \
1023
0
      for (j = 0; j < vector->rnum; j++) \
1024
0
        if (_while_get(vector->data.u8, j, 0) != 0) \
1025
0
          nnz++; \
1026
0
      ccv_matrix_getter(mat->type, while_block);
1027
0
#undef while_block
1028
0
    } else
1029
3
      nnz += vector->rnum;
1030
3
  }
1031
1
  ccv_compressed_sparse_matrix_t* cm = *csm = (ccv_compressed_sparse_matrix_t*)ccmalloc(sizeof(ccv_compressed_sparse_matrix_t) + nnz * sizeof(int) + nnz * CCV_GET_DATA_TYPE_SIZE(mat->type) + (((mat->major == CCV_SPARSE_COL_MAJOR) ? 
mat->cols0
: mat->rows) + 1) * sizeof(int));
1032
1
  cm->type = (mat->type & ~CCV_MATRIX_SPARSE & ~CCV_SPARSE_VECTOR & ~CCV_DENSE_VECTOR) | ((mat->major == CCV_SPARSE_COL_MAJOR) ? 
CCV_MATRIX_CSC0
: CCV_MATRIX_CSR);
1033
1
  cm->nnz = nnz;
1034
1
  cm->rows = mat->rows;
1035
1
  cm->cols = mat->cols;
1036
1
  cm->index = (int*)(cm + 1);
1037
1
  cm->offset = cm->index + nnz;
1038
1
  cm->data.i32 = cm->offset + ((mat->major == CCV_SPARSE_COL_MAJOR) ? 
mat->cols0
: mat->rows) + 1;
1039
1
  unsigned char* m_ptr = cm->data.u8;
1040
1
  int* idx = cm->index;
1041
1
  cm->offset[0] = 0;
1042
1
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
1043
1
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
1044
4
  for (i = 0; i < ((mat->major == CCV_SPARSE_COL_MAJOR) ? 
mat->cols0
: mat->rows);
i++3
)
1045
3
  {
1046
3
    ccv_sparse_matrix_vector_t* vector = ccv_get_sparse_matrix_vector(mat, i);
1047
3
    if (!vector || !vector->rnum)
1048
0
      cm->offset[i + 1] = cm->offset[i];
1049
3
    else {
1050
3
      if (mat->type & CCV_DENSE_VECTOR)
1051
0
      {
1052
0
        int k = 0;
1053
0
#define for_block(_, _for_set, _for_get) \
1054
0
        for (j = 0; j < vector->rnum; j++) \
1055
0
          if (_for_get(vector->data.u8, j, 0) != 0) \
1056
0
          { \
1057
0
            _for_set(m_ptr, k, _for_get(vector->data.u8, j)); \
1058
0
            idx[k] = j; \
1059
0
            k++; \
1060
0
          }
1061
0
        ccv_matrix_setter_getter(mat->type, for_block);
1062
0
#undef for_block
1063
0
        cm->offset[i + 1] = cm->offset[i] + k;
1064
0
        idx += k;
1065
0
        m_ptr += k * CCV_GET_DATA_TYPE_SIZE(mat->type);
1066
3
      } else {
1067
3
        int k = 0;
1068
3
        uint8_t* const index = (uint8_t*)vector->index;
1069
3
#define for_block(_, _for_set, _for_get) \
1070
15
        
for (j = 0; 3
j < vector->size;
j++12
) \
1071
12
        { \
1072
12
          ccv_sparse_matrix_index_t* const index_j = (ccv_sparse_matrix_index_t*)(index + index_size * j); \
1073
12
          if (index_j->ifbit > 1) \
1074
12
          { \
1075
6
            _for_set(m_ptr, k, _for_get((uint8_t*)(index_j + 1), 0)); \
1076
6
            idx[k] = index_j->i; \
1077
6
            k++; \
1078
6
          } \
1079
12
        }
1080
3
        ccv_matrix_setter_getter(mat->type, for_block);
1081
3
#undef for_block
1082
3
        assert(k == vector->rnum);
1083
3
        switch (CCV_GET_DATA_TYPE(mat->type))
1084
3
        {
1085
0
          case CCV_8U:
1086
0
            _ccv_indice_uchar_sort(idx, vector->rnum, (unsigned char*)m_ptr);
1087
0
            break;
1088
0
          case CCV_32S:
1089
0
            _ccv_indice_int_sort(idx, vector->rnum, (int*)m_ptr);
1090
0
            break;
1091
3
          case CCV_32F:
1092
3
            _ccv_indice_float_sort(idx, vector->rnum, (float*)m_ptr);
1093
3
            break;
1094
0
          case CCV_64F:
1095
0
            _ccv_indice_double_sort(idx, vector->rnum, (double*)m_ptr);
1096
0
            break;
1097
3
        }
1098
3
        cm->offset[i + 1] = cm->offset[i] + vector->rnum;
1099
3
        idx += vector->rnum;
1100
3
        m_ptr += vector->rnum * CCV_GET_DATA_TYPE_SIZE(mat->type);
1101
3
      }
1102
3
    }
1103
3
  }
1104
1
}
1105
1106
void ccv_decompress_sparse_matrix(const ccv_compressed_sparse_matrix_t* csm, ccv_sparse_matrix_t** smt)
1107
1
{
1108
1
  ccv_sparse_matrix_t* mat = *smt = ccv_sparse_matrix_new(csm->rows, csm->cols, csm->type & ~CCV_MATRIX_CSR & ~CCV_MATRIX_CSC, (csm->type & CCV_MATRIX_CSR) ? CCV_SPARSE_ROW_MAJOR : 
CCV_SPARSE_COL_MAJOR0
, 0);
1109
1
  int i, j;
1110
4
  for (i = 0; i < ((mat->major == CCV_SPARSE_COL_MAJOR) ? 
mat->cols0
: mat->rows);
i++3
)
1111
9
    
for (j = csm->offset[i]; 3
j < csm->offset[i + 1];
j++6
)
1112
6
      if (mat->major == CCV_SPARSE_COL_MAJOR)
1113
0
        ccv_set_sparse_matrix_cell(mat, csm->index[j], i, csm->data.u8 + CCV_GET_DATA_TYPE_SIZE(csm->type) * j);
1114
6
      else
1115
6
        ccv_set_sparse_matrix_cell(mat, i, csm->index[j], csm->data.u8 + CCV_GET_DATA_TYPE_SIZE(csm->type) * j);
1116
1
}
1117
1118
int ccv_matrix_eq(ccv_matrix_t* a, ccv_matrix_t* b)
1119
177
{
1120
177
  int a_type = *(int*)a;
1121
177
  int b_type = *(int*)b;
1122
177
  if ((a_type & CCV_MATRIX_DENSE) && (b_type & CCV_MATRIX_DENSE))
1123
177
  {
1124
177
    ccv_dense_matrix_t* da = (ccv_dense_matrix_t*)a;
1125
177
    ccv_dense_matrix_t* db = (ccv_dense_matrix_t*)b;
1126
177
    if (CCV_GET_DATA_TYPE(da->type) != CCV_GET_DATA_TYPE(db->type))
1127
177
      
return -10
;
1128
177
    if (CCV_GET_CHANNEL(da->type) != CCV_GET_CHANNEL(db->type))
1129
177
      
return -10
;
1130
177
    if (da->rows != db->rows)
1131
0
      return -1;
1132
177
    if (da->cols != db->cols)
1133
0
      return -1;
1134
177
    int i, j, ch = CCV_GET_CHANNEL(da->type);
1135
177
    unsigned char* a_ptr = da->data.u8;
1136
177
    unsigned char* b_ptr = db->data.u8;
1137
177
    // Read: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
1138
177
    // http://floating-point-gui.de/errors/comparison/
1139
177
    if (CCV_GET_DATA_TYPE(db->type) == CCV_32F)
1140
150
    {
1141
150
      static const float epsi = FLT_EPSILON;
1142
150
      static const int32_t ulps = 128; // So that for 1 and 1.000015 will be treated as the same.
1143
13.6k
      for (i = 0; i < da->rows; 
i++13.5k
)
1144
13.5k
      {
1145
13.5k
        int32_t* ia_ptr = (int32_t*)a_ptr;
1146
13.5k
        int32_t* ib_ptr = (int32_t*)b_ptr;
1147
25.7M
        for (j = 0; j < da->cols * ch; 
j++25.6M
)
1148
25.6M
        {
1149
25.6M
          int32_t i32a = ia_ptr[j];
1150
25.6M
          if (i32a < 0)
1151
9.68k
            i32a = 0x80000000 - i32a;
1152
25.6M
          int32_t i32b = ib_ptr[j];
1153
25.6M
          if (i32b < 0)
1154
9.68k
            i32b = 0x80000000 - i32b;
1155
25.6M
          if (abs(i32a - i32b) > ulps && 
fabsf(((float*)a_ptr)[j] - ((float*)b_ptr)[j]) > epsi0
)
1156
0
            return -1;
1157
25.6M
        }
1158
13.5k
        a_ptr += da->step;
1159
13.5k
        b_ptr += db->step;
1160
13.5k
      }
1161
150
    } else 
if (27
CCV_GET_DATA_TYPE27
(db->type) == CCV_64F27
) {
1162
1
      static const double epsi = FLT_EPSILON; // Using FLT_EPSILON because for most of ccv computations, we have 32-bit float point computation inside.
1163
1
      static const int64_t ulps = 0x100000l; // So that for 1 and 1.000000001 will be treated as the same.
1164
254
      for (i = 0; i < da->rows; 
i++253
)
1165
253
      {
1166
253
        int64_t* ia_ptr = (int64_t*)a_ptr;
1167
253
        int64_t* ib_ptr = (int64_t*)b_ptr;
1168
144k
        for (j = 0; j < da->cols * ch; 
j++144k
)
1169
144k
        {
1170
144k
          int64_t i64a = ia_ptr[j];
1171
144k
          if (i64a < 0)
1172
0
            i64a = 0x8000000000000000l - i64a;
1173
144k
          int64_t i64b = ib_ptr[j];
1174
144k
          if (i64b < 0)
1175
0
            i64b = 0x8000000000000000l - i64b;
1176
144k
          if (llabs(i64a - i64b) > ulps && 
fabsf(((float*)a_ptr)[j] - ((float*)b_ptr)[j]) > epsi1
)
1177
0
            return -1;
1178
144k
        }
1179
253
        a_ptr += da->step;
1180
253
        b_ptr += db->step;
1181
253
      }
1182
26
    } else {
1183
26
#define for_block(_, _for_get) \
1184
14.0k
      
for (i = 0; 26
i < da->rows;
i++14.0k
) \
1185
14.0k
      { \
1186
31.1M
        for (j = 0; j < da->cols * ch; 
j++31.1M
) \
1187
31.1M
        { \
1188
31.1M
          if (llabs(_for_get(b_ptr, j) - _for_get(a_ptr, j)) > 1) { \
1189
0
            printf("%d %d\n", (int)_for_get(b_ptr, j), (int)_for_get(a_ptr, j)); \
1190
0
            return -1; \
1191
0
          } \
1192
31.1M
        } \
1193
14.0k
        a_ptr += da->step; \
1194
14.0k
        b_ptr += db->step; \
1195
14.0k
      }
1196
26
      ccv_matrix_getter_integer_only(da->type, for_block);
1197
26
#undef for_block
1198
26
    }
1199
177
  }
1200
177
  return 0;
1201
177
}
1202
1203
void ccv_slice(ccv_matrix_t* a, ccv_matrix_t** b, int btype, int y, int x, int rows, int cols)
1204
148k
{
1205
148k
  int type = *(int*)a;
1206
148k
  if (type & CCV_MATRIX_DENSE)
1207
148k
  {
1208
148k
    ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
1209
148k
    ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(128, "ccv_slice(%d,%d,%d,%d)", y, x, rows, cols), da->sig, CCV_EOF_SIGN);
1210
18.4E
    btype = (btype == 0) ? 
CCV_GET_DATA_TYPE149k
(da->type) | 149k
CCV_GET_CHANNEL149k
(da->type) : CCV_GET_DATA_TYPE(btype) | CCV_GET_CHANNEL(da->type);
1211
148k
    ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, rows, cols, CCV_ALL_DATA_TYPE | CCV_GET_CHANNEL(da->type), btype, sig);
1212
148k
    ccv_object_return_if_cached(, db);
1213
148k
    int i, j, ch = CCV_GET_CHANNEL(da->type);
1214
148k
    int dx = 0, dy = 0;
1215
148k
    if (!(y >= 0 && 
y + rows <= da->rows148k
&&
x >= 0148k
&&
x + cols <= da->cols148k
))
1216
1
    {
1217
1
      ccv_zero(db);
1218
1
      if (y < 0) { rows += y; dy = -y; y = 0; }
1219
1
      if (y + rows > da->rows) rows = da->rows - y;
1220
1
      if (x < 0) 
{ cols += x; dx = -x; x = 0; }0
1221
1
      if (x + cols > da->cols) 
cols = da->cols - x0
;
1222
1
    }
1223
148k
    unsigned char* a_ptr = da->data.u8 + x * ch * CCV_GET_DATA_TYPE_SIZE(da->type) + y * da->step;
1224
148k
    unsigned char* b_ptr = db->data.u8 + dx * ch * CCV_GET_DATA_TYPE_SIZE(db->type) + dy * db->step;
1225
148k
#define for_block(_for_set, _for_get) \
1226
3.63M
    
for (i = 0; 146k
i < rows;
i++3.48M
) \
1227
3.48M
    { \
1228
101M
      for (j = 0; j < cols * ch; 
j++97.7M
) \
1229
97.7M
      { \
1230
97.7M
        _for_set(b_ptr, j, _for_get(a_ptr, j)); \
1231
97.7M
      } \
1232
3.48M
      a_ptr += da->step; \
1233
3.48M
      b_ptr += db->step; \
1234
3.48M
    }
1235
148k
    ccv_matrix_setter(db->type, 
ccv_matrix_getter146k
, da->type,
for_block146k
);
1236
145k
#undef for_block
1237
18.4E
  } else if (type & CCV_MATRIX_SPARSE) {
1238
0
  }
1239
148k
}
1240
1241
ccv_dense_matrix_t ccv_reshape(ccv_dense_matrix_t* a, int y, int x, int rows, int cols)
1242
1
{
1243
1
  assert(y + rows <= a->rows);
1244
1
  assert(x + cols <= a->cols);
1245
1
  assert(x >= 0 && y >= 0);
1246
1
  ccv_dense_matrix_t b = {
1247
1
    .type = (CCV_UNMANAGED | CCV_GET_DATA_TYPE(a->type) | CCV_GET_CHANNEL(a->type) | CCV_NO_DATA_ALLOC | CCV_MATRIX_DENSE) & ~CCV_GARBAGE,
1248
1
    .rows = rows,
1249
1
    .cols = cols,
1250
1
    .step = a->step,
1251
1
    .refcount = 0,
1252
1
    .sig = 0,
1253
1
    .tb.u8 = 0,
1254
1
    .data.u8 = ccv_get_dense_matrix_cell(a, y, x, 0),
1255
1
  };
1256
1
  return b;
1257
1
}
1258
1259
void ccv_move(ccv_matrix_t* a, ccv_matrix_t** b, int btype, int y, int x)
1260
0
{
1261
0
  int type = *(int*)a;
1262
0
  if (type & CCV_MATRIX_DENSE)
1263
0
  {
1264
0
    ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
1265
0
    ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_move(%d,%d)", y, x), da->sig, CCV_EOF_SIGN);
1266
0
    btype = (btype == 0) ? CCV_GET_DATA_TYPE(da->type) | CCV_GET_CHANNEL(da->type) : CCV_GET_DATA_TYPE(btype) | CCV_GET_CHANNEL(da->type);
1267
0
    ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_ALL_DATA_TYPE | CCV_GET_CHANNEL(da->type), btype, sig);
1268
0
    ccv_object_return_if_cached(, db);
1269
0
    int i, j, ch = CCV_GET_CHANNEL(da->type);
1270
0
    unsigned char* a_ptr = da->data.u8 + ccv_max(x, 0) * ch * CCV_GET_DATA_TYPE_SIZE(da->type) + ccv_max(y, 0) * da->step;
1271
0
    unsigned char* b_ptr = db->data.u8 + ccv_max(-x, 0) * ch * CCV_GET_DATA_TYPE_SIZE(db->type) + ccv_max(-y, 0) * db->step;
1272
0
#define for_block(_for_set, _for_get) \
1273
0
    for (i = abs(y); i < db->rows; i++) \
1274
0
    { \
1275
0
      for (j = abs(x) * ch; j < db->cols * ch; j++) \
1276
0
      { \
1277
0
        _for_set(b_ptr, j, _for_get(a_ptr, j)); \
1278
0
      } \
1279
0
      a_ptr += da->step; \
1280
0
      b_ptr += db->step; \
1281
0
    }
1282
0
    ccv_matrix_setter(db->type, ccv_matrix_getter, da->type, for_block);
1283
0
#undef for_block
1284
0
  } else if (type & CCV_MATRIX_SPARSE) {
1285
0
  }
1286
0
}
1287
1288
// the code are shamelessly copied from ftp://ftp.fox-toolkit.org/pub/fasthalffloatconversion.pdf, assuming in Public Domain
1289
1290
static uint16_t _ccv_base_table[512] = {
1291
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1292
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1293
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1294
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1295
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1296
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1297
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100,
1298
  0x200, 0x400, 0x800, 0xc00, 0x1000, 0x1400, 0x1800, 0x1c00, 0x2000, 0x2400, 0x2800, 0x2c00, 0x3000, 0x3400, 0x3800, 0x3c00,
1299
  0x4000, 0x4400, 0x4800, 0x4c00, 0x5000, 0x5400, 0x5800, 0x5c00, 0x6000, 0x6400, 0x6800, 0x6c00, 0x7000, 0x7400, 0x7800, 0x7c00,
1300
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1301
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1302
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1303
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1304
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1305
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1306
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1307
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1308
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1309
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1310
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1311
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1312
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1313
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8001, 0x8002, 0x8004, 0x8008, 0x8010, 0x8020, 0x8040, 0x8080, 0x8100,
1314
  0x8200, 0x8400, 0x8800, 0x8c00, 0x9000, 0x9400, 0x9800, 0x9c00, 0xa000, 0xa400, 0xa800, 0xac00, 0xb000, 0xb400, 0xb800, 0xbc00,
1315
  0xc000, 0xc400, 0xc800, 0xcc00, 0xd000, 0xd400, 0xd800, 0xdc00, 0xe000, 0xe400, 0xe800, 0xec00, 0xf000, 0xf400, 0xf800, 0xfc00,
1316
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1317
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1318
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1319
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1320
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1321
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1322
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1323
};
1324
1325
static uint8_t _ccv_shift_table[512] = {
1326
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1327
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1328
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1329
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1330
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1331
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1332
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0xf,
1333
  0xe, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd,
1334
  0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0x18,
1335
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1336
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1337
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1338
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1339
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1340
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1341
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0xd,
1342
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1343
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1344
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1345
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1346
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1347
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1348
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0xf,
1349
  0xe, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd,
1350
  0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0x18,
1351
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1352
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1353
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1354
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1355
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1356
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1357
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0xd,
1358
};
1359
1360
void ccv_float_to_half_precision(float* f, uint16_t* h, size_t len)
1361
19.9M
{
1362
19.9M
  int i;
1363
19.9M
  uint32_t* u = (uint32_t*)f;
1364
872M
  for (i = 0; i < len; 
i++852M
)
1365
852M
    h[i] = _ccv_base_table[(u[i] >> 23) & 0x1ff] + ((u[i] & 0x007fffff) >> _ccv_shift_table[(u[i] >> 23) & 0x1ff]);
1366
19.9M
}
1367
1368
void ccv_double_to_half_precision(double* f, uint16_t* h, size_t len)
1369
2
{
1370
2
  int i;
1371
258
  for (i = 0; i < len; 
i++256
)
1372
256
  {
1373
256
    union {
1374
256
      float v;
1375
256
      uint32_t p;
1376
256
    } u = { .v = (float)f[i] };
1377
256
    h[i] = _ccv_base_table[(u.p >> 23) & 0x1ff] + ((u.p & 0x007fffff) >> _ccv_shift_table[(u.p >> 23) & 0x1ff]);
1378
256
  }
1379
2
}
1380
1381
static uint32_t _ccv_mantissa_table[2048] = {
1382
  0x0, 0x33800000, 0x34000000, 0x34400000, 0x34800000, 0x34a00000, 0x34c00000, 0x34e00000,
1383
  0x35000000, 0x35100000, 0x35200000, 0x35300000, 0x35400000, 0x35500000, 0x35600000, 0x35700000,
1384
  0x35800000, 0x35880000, 0x35900000, 0x35980000, 0x35a00000, 0x35a80000, 0x35b00000, 0x35b80000,
1385
  0x35c00000, 0x35c80000, 0x35d00000, 0x35d80000, 0x35e00000, 0x35e80000, 0x35f00000, 0x35f80000,
1386
  0x36000000, 0x36040000, 0x36080000, 0x360c0000, 0x36100000, 0x36140000, 0x36180000, 0x361c0000,
1387
  0x36200000, 0x36240000, 0x36280000, 0x362c0000, 0x36300000, 0x36340000, 0x36380000, 0x363c0000,
1388
  0x36400000, 0x36440000, 0x36480000, 0x364c0000, 0x36500000, 0x36540000, 0x36580000, 0x365c0000,
1389
  0x36600000, 0x36640000, 0x36680000, 0x366c0000, 0x36700000, 0x36740000, 0x36780000, 0x367c0000,
1390
  0x36800000, 0x36820000, 0x36840000, 0x36860000, 0x36880000, 0x368a0000, 0x368c0000, 0x368e0000,
1391
  0x36900000, 0x36920000, 0x36940000, 0x36960000, 0x36980000, 0x369a0000, 0x369c0000, 0x369e0000,
1392
  0x36a00000, 0x36a20000, 0x36a40000, 0x36a60000, 0x36a80000, 0x36aa0000, 0x36ac0000, 0x36ae0000,
1393
  0x36b00000, 0x36b20000, 0x36b40000, 0x36b60000, 0x36b80000, 0x36ba0000, 0x36bc0000, 0x36be0000,
1394
  0x36c00000, 0x36c20000, 0x36c40000, 0x36c60000, 0x36c80000, 0x36ca0000, 0x36cc0000, 0x36ce0000,
1395
  0x36d00000, 0x36d20000, 0x36d40000, 0x36d60000, 0x36d80000, 0x36da0000, 0x36dc0000, 0x36de0000,
1396
  0x36e00000, 0x36e20000, 0x36e40000, 0x36e60000, 0x36e80000, 0x36ea0000, 0x36ec0000, 0x36ee0000,
1397
  0x36f00000, 0x36f20000, 0x36f40000, 0x36f60000, 0x36f80000, 0x36fa0000, 0x36fc0000, 0x36fe0000,
1398
  0x37000000, 0x37010000, 0x37020000, 0x37030000, 0x37040000, 0x37050000, 0x37060000, 0x37070000,
1399
  0x37080000, 0x37090000, 0x370a0000, 0x370b0000, 0x370c0000, 0x370d0000, 0x370e0000, 0x370f0000,
1400
  0x37100000, 0x37110000, 0x37120000, 0x37130000, 0x37140000, 0x37150000, 0x37160000, 0x37170000,
1401
  0x37180000, 0x37190000, 0x371a0000, 0x371b0000, 0x371c0000, 0x371d0000, 0x371e0000, 0x371f0000,
1402
  0x37200000, 0x37210000, 0x37220000, 0x37230000, 0x37240000, 0x37250000, 0x37260000, 0x37270000,
1403
  0x37280000, 0x37290000, 0x372a0000, 0x372b0000, 0x372c0000, 0x372d0000, 0x372e0000, 0x372f0000,
1404
  0x37300000, 0x37310000, 0x37320000, 0x37330000, 0x37340000, 0x37350000, 0x37360000, 0x37370000,
1405
  0x37380000, 0x37390000, 0x373a0000, 0x373b0000, 0x373c0000, 0x373d0000, 0x373e0000, 0x373f0000,
1406
  0x37400000, 0x37410000, 0x37420000, 0x37430000, 0x37440000, 0x37450000, 0x37460000, 0x37470000,
1407
  0x37480000, 0x37490000, 0x374a0000, 0x374b0000, 0x374c0000, 0x374d0000, 0x374e0000, 0x374f0000,
1408
  0x37500000, 0x37510000, 0x37520000, 0x37530000, 0x37540000, 0x37550000, 0x37560000, 0x37570000,
1409
  0x37580000, 0x37590000, 0x375a0000, 0x375b0000, 0x375c0000, 0x375d0000, 0x375e0000, 0x375f0000,
1410
  0x37600000, 0x37610000, 0x37620000, 0x37630000, 0x37640000, 0x37650000, 0x37660000, 0x37670000,
1411
  0x37680000, 0x37690000, 0x376a0000, 0x376b0000, 0x376c0000, 0x376d0000, 0x376e0000, 0x376f0000,
1412
  0x37700000, 0x37710000, 0x37720000, 0x37730000, 0x37740000, 0x37750000, 0x37760000, 0x37770000,
1413
  0x37780000, 0x37790000, 0x377a0000, 0x377b0000, 0x377c0000, 0x377d0000, 0x377e0000, 0x377f0000,
1414
  0x37800000, 0x37808000, 0x37810000, 0x37818000, 0x37820000, 0x37828000, 0x37830000, 0x37838000,
1415
  0x37840000, 0x37848000, 0x37850000, 0x37858000, 0x37860000, 0x37868000, 0x37870000, 0x37878000,
1416
  0x37880000, 0x37888000, 0x37890000, 0x37898000, 0x378a0000, 0x378a8000, 0x378b0000, 0x378b8000,
1417
  0x378c0000, 0x378c8000, 0x378d0000, 0x378d8000, 0x378e0000, 0x378e8000, 0x378f0000, 0x378f8000,
1418
  0x37900000, 0x37908000, 0x37910000, 0x37918000, 0x37920000, 0x37928000, 0x37930000, 0x37938000,
1419
  0x37940000, 0x37948000, 0x37950000, 0x37958000, 0x37960000, 0x37968000, 0x37970000, 0x37978000,
1420
  0x37980000, 0x37988000, 0x37990000, 0x37998000, 0x379a0000, 0x379a8000, 0x379b0000, 0x379b8000,
1421
  0x379c0000, 0x379c8000, 0x379d0000, 0x379d8000, 0x379e0000, 0x379e8000, 0x379f0000, 0x379f8000,
1422
  0x37a00000, 0x37a08000, 0x37a10000, 0x37a18000, 0x37a20000, 0x37a28000, 0x37a30000, 0x37a38000,
1423
  0x37a40000, 0x37a48000, 0x37a50000, 0x37a58000, 0x37a60000, 0x37a68000, 0x37a70000, 0x37a78000,
1424
  0x37a80000, 0x37a88000, 0x37a90000, 0x37a98000, 0x37aa0000, 0x37aa8000, 0x37ab0000, 0x37ab8000,
1425
  0x37ac0000, 0x37ac8000, 0x37ad0000, 0x37ad8000, 0x37ae0000, 0x37ae8000, 0x37af0000, 0x37af8000,
1426
  0x37b00000, 0x37b08000, 0x37b10000, 0x37b18000, 0x37b20000, 0x37b28000, 0x37b30000, 0x37b38000,
1427
  0x37b40000, 0x37b48000, 0x37b50000, 0x37b58000, 0x37b60000, 0x37b68000, 0x37b70000, 0x37b78000,
1428
  0x37b80000, 0x37b88000, 0x37b90000, 0x37b98000, 0x37ba0000, 0x37ba8000, 0x37bb0000, 0x37bb8000,
1429
  0x37bc0000, 0x37bc8000, 0x37bd0000, 0x37bd8000, 0x37be0000, 0x37be8000, 0x37bf0000, 0x37bf8000,
1430
  0x37c00000, 0x37c08000, 0x37c10000, 0x37c18000, 0x37c20000, 0x37c28000, 0x37c30000, 0x37c38000,
1431
  0x37c40000, 0x37c48000, 0x37c50000, 0x37c58000, 0x37c60000, 0x37c68000, 0x37c70000, 0x37c78000,
1432
  0x37c80000, 0x37c88000, 0x37c90000, 0x37c98000, 0x37ca0000, 0x37ca8000, 0x37cb0000, 0x37cb8000,
1433
  0x37cc0000, 0x37cc8000, 0x37cd0000, 0x37cd8000, 0x37ce0000, 0x37ce8000, 0x37cf0000, 0x37cf8000,
1434
  0x37d00000, 0x37d08000, 0x37d10000, 0x37d18000, 0x37d20000, 0x37d28000, 0x37d30000, 0x37d38000,
1435
  0x37d40000, 0x37d48000, 0x37d50000, 0x37d58000, 0x37d60000, 0x37d68000, 0x37d70000, 0x37d78000,
1436
  0x37d80000, 0x37d88000, 0x37d90000, 0x37d98000, 0x37da0000, 0x37da8000, 0x37db0000, 0x37db8000,
1437
  0x37dc0000, 0x37dc8000, 0x37dd0000, 0x37dd8000, 0x37de0000, 0x37de8000, 0x37df0000, 0x37df8000,
1438
  0x37e00000, 0x37e08000, 0x37e10000, 0x37e18000, 0x37e20000, 0x37e28000, 0x37e30000, 0x37e38000,
1439
  0x37e40000, 0x37e48000, 0x37e50000, 0x37e58000, 0x37e60000, 0x37e68000, 0x37e70000, 0x37e78000,
1440
  0x37e80000, 0x37e88000, 0x37e90000, 0x37e98000, 0x37ea0000, 0x37ea8000, 0x37eb0000, 0x37eb8000,
1441
  0x37ec0000, 0x37ec8000, 0x37ed0000, 0x37ed8000, 0x37ee0000, 0x37ee8000, 0x37ef0000, 0x37ef8000,
1442
  0x37f00000, 0x37f08000, 0x37f10000, 0x37f18000, 0x37f20000, 0x37f28000, 0x37f30000, 0x37f38000,
1443
  0x37f40000, 0x37f48000, 0x37f50000, 0x37f58000, 0x37f60000, 0x37f68000, 0x37f70000, 0x37f78000,
1444
  0x37f80000, 0x37f88000, 0x37f90000, 0x37f98000, 0x37fa0000, 0x37fa8000, 0x37fb0000, 0x37fb8000,
1445
  0x37fc0000, 0x37fc8000, 0x37fd0000, 0x37fd8000, 0x37fe0000, 0x37fe8000, 0x37ff0000, 0x37ff8000,
1446
  0x38000000, 0x38004000, 0x38008000, 0x3800c000, 0x38010000, 0x38014000, 0x38018000, 0x3801c000,
1447
  0x38020000, 0x38024000, 0x38028000, 0x3802c000, 0x38030000, 0x38034000, 0x38038000, 0x3803c000,
1448
  0x38040000, 0x38044000, 0x38048000, 0x3804c000, 0x38050000, 0x38054000, 0x38058000, 0x3805c000,
1449
  0x38060000, 0x38064000, 0x38068000, 0x3806c000, 0x38070000, 0x38074000, 0x38078000, 0x3807c000,
1450
  0x38080000, 0x38084000, 0x38088000, 0x3808c000, 0x38090000, 0x38094000, 0x38098000, 0x3809c000,
1451
  0x380a0000, 0x380a4000, 0x380a8000, 0x380ac000, 0x380b0000, 0x380b4000, 0x380b8000, 0x380bc000,
1452
  0x380c0000, 0x380c4000, 0x380c8000, 0x380cc000, 0x380d0000, 0x380d4000, 0x380d8000, 0x380dc000,
1453
  0x380e0000, 0x380e4000, 0x380e8000, 0x380ec000, 0x380f0000, 0x380f4000, 0x380f8000, 0x380fc000,
1454
  0x38100000, 0x38104000, 0x38108000, 0x3810c000, 0x38110000, 0x38114000, 0x38118000, 0x3811c000,
1455
  0x38120000, 0x38124000, 0x38128000, 0x3812c000, 0x38130000, 0x38134000, 0x38138000, 0x3813c000,
1456
  0x38140000, 0x38144000, 0x38148000, 0x3814c000, 0x38150000, 0x38154000, 0x38158000, 0x3815c000,
1457
  0x38160000, 0x38164000, 0x38168000, 0x3816c000, 0x38170000, 0x38174000, 0x38178000, 0x3817c000,
1458
  0x38180000, 0x38184000, 0x38188000, 0x3818c000, 0x38190000, 0x38194000, 0x38198000, 0x3819c000,
1459
  0x381a0000, 0x381a4000, 0x381a8000, 0x381ac000, 0x381b0000, 0x381b4000, 0x381b8000, 0x381bc000,
1460
  0x381c0000, 0x381c4000, 0x381c8000, 0x381cc000, 0x381d0000, 0x381d4000, 0x381d8000, 0x381dc000,
1461
  0x381e0000, 0x381e4000, 0x381e8000, 0x381ec000, 0x381f0000, 0x381f4000, 0x381f8000, 0x381fc000,
1462
  0x38200000, 0x38204000, 0x38208000, 0x3820c000, 0x38210000, 0x38214000, 0x38218000, 0x3821c000,
1463
  0x38220000, 0x38224000, 0x38228000, 0x3822c000, 0x38230000, 0x38234000, 0x38238000, 0x3823c000,
1464
  0x38240000, 0x38244000, 0x38248000, 0x3824c000, 0x38250000, 0x38254000, 0x38258000, 0x3825c000,
1465
  0x38260000, 0x38264000, 0x38268000, 0x3826c000, 0x38270000, 0x38274000, 0x38278000, 0x3827c000,
1466
  0x38280000, 0x38284000, 0x38288000, 0x3828c000, 0x38290000, 0x38294000, 0x38298000, 0x3829c000,
1467
  0x382a0000, 0x382a4000, 0x382a8000, 0x382ac000, 0x382b0000, 0x382b4000, 0x382b8000, 0x382bc000,
1468
  0x382c0000, 0x382c4000, 0x382c8000, 0x382cc000, 0x382d0000, 0x382d4000, 0x382d8000, 0x382dc000,
1469
  0x382e0000, 0x382e4000, 0x382e8000, 0x382ec000, 0x382f0000, 0x382f4000, 0x382f8000, 0x382fc000,
1470
  0x38300000, 0x38304000, 0x38308000, 0x3830c000, 0x38310000, 0x38314000, 0x38318000, 0x3831c000,
1471
  0x38320000, 0x38324000, 0x38328000, 0x3832c000, 0x38330000, 0x38334000, 0x38338000, 0x3833c000,
1472
  0x38340000, 0x38344000, 0x38348000, 0x3834c000, 0x38350000, 0x38354000, 0x38358000, 0x3835c000,
1473
  0x38360000, 0x38364000, 0x38368000, 0x3836c000, 0x38370000, 0x38374000, 0x38378000, 0x3837c000,
1474
  0x38380000, 0x38384000, 0x38388000, 0x3838c000, 0x38390000, 0x38394000, 0x38398000, 0x3839c000,
1475
  0x383a0000, 0x383a4000, 0x383a8000, 0x383ac000, 0x383b0000, 0x383b4000, 0x383b8000, 0x383bc000,
1476
  0x383c0000, 0x383c4000, 0x383c8000, 0x383cc000, 0x383d0000, 0x383d4000, 0x383d8000, 0x383dc000,
1477
  0x383e0000, 0x383e4000, 0x383e8000, 0x383ec000, 0x383f0000, 0x383f4000, 0x383f8000, 0x383fc000,
1478
  0x38400000, 0x38404000, 0x38408000, 0x3840c000, 0x38410000, 0x38414000, 0x38418000, 0x3841c000,
1479
  0x38420000, 0x38424000, 0x38428000, 0x3842c000, 0x38430000, 0x38434000, 0x38438000, 0x3843c000,
1480
  0x38440000, 0x38444000, 0x38448000, 0x3844c000, 0x38450000, 0x38454000, 0x38458000, 0x3845c000,
1481
  0x38460000, 0x38464000, 0x38468000, 0x3846c000, 0x38470000, 0x38474000, 0x38478000, 0x3847c000,
1482
  0x38480000, 0x38484000, 0x38488000, 0x3848c000, 0x38490000, 0x38494000, 0x38498000, 0x3849c000,
1483
  0x384a0000, 0x384a4000, 0x384a8000, 0x384ac000, 0x384b0000, 0x384b4000, 0x384b8000, 0x384bc000,
1484
  0x384c0000, 0x384c4000, 0x384c8000, 0x384cc000, 0x384d0000, 0x384d4000, 0x384d8000, 0x384dc000,
1485
  0x384e0000, 0x384e4000, 0x384e8000, 0x384ec000, 0x384f0000, 0x384f4000, 0x384f8000, 0x384fc000,
1486
  0x38500000, 0x38504000, 0x38508000, 0x3850c000, 0x38510000, 0x38514000, 0x38518000, 0x3851c000,
1487
  0x38520000, 0x38524000, 0x38528000, 0x3852c000, 0x38530000, 0x38534000, 0x38538000, 0x3853c000,
1488
  0x38540000, 0x38544000, 0x38548000, 0x3854c000, 0x38550000, 0x38554000, 0x38558000, 0x3855c000,
1489
  0x38560000, 0x38564000, 0x38568000, 0x3856c000, 0x38570000, 0x38574000, 0x38578000, 0x3857c000,
1490
  0x38580000, 0x38584000, 0x38588000, 0x3858c000, 0x38590000, 0x38594000, 0x38598000, 0x3859c000,
1491
  0x385a0000, 0x385a4000, 0x385a8000, 0x385ac000, 0x385b0000, 0x385b4000, 0x385b8000, 0x385bc000,
1492
  0x385c0000, 0x385c4000, 0x385c8000, 0x385cc000, 0x385d0000, 0x385d4000, 0x385d8000, 0x385dc000,
1493
  0x385e0000, 0x385e4000, 0x385e8000, 0x385ec000, 0x385f0000, 0x385f4000, 0x385f8000, 0x385fc000,
1494
  0x38600000, 0x38604000, 0x38608000, 0x3860c000, 0x38610000, 0x38614000, 0x38618000, 0x3861c000,
1495
  0x38620000, 0x38624000, 0x38628000, 0x3862c000, 0x38630000, 0x38634000, 0x38638000, 0x3863c000,
1496
  0x38640000, 0x38644000, 0x38648000, 0x3864c000, 0x38650000, 0x38654000, 0x38658000, 0x3865c000,
1497
  0x38660000, 0x38664000, 0x38668000, 0x3866c000, 0x38670000, 0x38674000, 0x38678000, 0x3867c000,
1498
  0x38680000, 0x38684000, 0x38688000, 0x3868c000, 0x38690000, 0x38694000, 0x38698000, 0x3869c000,
1499
  0x386a0000, 0x386a4000, 0x386a8000, 0x386ac000, 0x386b0000, 0x386b4000, 0x386b8000, 0x386bc000,
1500
  0x386c0000, 0x386c4000, 0x386c8000, 0x386cc000, 0x386d0000, 0x386d4000, 0x386d8000, 0x386dc000,
1501
  0x386e0000, 0x386e4000, 0x386e8000, 0x386ec000, 0x386f0000, 0x386f4000, 0x386f8000, 0x386fc000,
1502
  0x38700000, 0x38704000, 0x38708000, 0x3870c000, 0x38710000, 0x38714000, 0x38718000, 0x3871c000,
1503
  0x38720000, 0x38724000, 0x38728000, 0x3872c000, 0x38730000, 0x38734000, 0x38738000, 0x3873c000,
1504
  0x38740000, 0x38744000, 0x38748000, 0x3874c000, 0x38750000, 0x38754000, 0x38758000, 0x3875c000,
1505
  0x38760000, 0x38764000, 0x38768000, 0x3876c000, 0x38770000, 0x38774000, 0x38778000, 0x3877c000,
1506
  0x38780000, 0x38784000, 0x38788000, 0x3878c000, 0x38790000, 0x38794000, 0x38798000, 0x3879c000,
1507
  0x387a0000, 0x387a4000, 0x387a8000, 0x387ac000, 0x387b0000, 0x387b4000, 0x387b8000, 0x387bc000,
1508
  0x387c0000, 0x387c4000, 0x387c8000, 0x387cc000, 0x387d0000, 0x387d4000, 0x387d8000, 0x387dc000,
1509
  0x387e0000, 0x387e4000, 0x387e8000, 0x387ec000, 0x387f0000, 0x387f4000, 0x387f8000, 0x387fc000,
1510
  0x38000000, 0x38002000, 0x38004000, 0x38006000, 0x38008000, 0x3800a000, 0x3800c000, 0x3800e000,
1511
  0x38010000, 0x38012000, 0x38014000, 0x38016000, 0x38018000, 0x3801a000, 0x3801c000, 0x3801e000,
1512
  0x38020000, 0x38022000, 0x38024000, 0x38026000, 0x38028000, 0x3802a000, 0x3802c000, 0x3802e000,
1513
  0x38030000, 0x38032000, 0x38034000, 0x38036000, 0x38038000, 0x3803a000, 0x3803c000, 0x3803e000,
1514
  0x38040000, 0x38042000, 0x38044000, 0x38046000, 0x38048000, 0x3804a000, 0x3804c000, 0x3804e000,
1515
  0x38050000, 0x38052000, 0x38054000, 0x38056000, 0x38058000, 0x3805a000, 0x3805c000, 0x3805e000,
1516
  0x38060000, 0x38062000, 0x38064000, 0x38066000, 0x38068000, 0x3806a000, 0x3806c000, 0x3806e000,
1517
  0x38070000, 0x38072000, 0x38074000, 0x38076000, 0x38078000, 0x3807a000, 0x3807c000, 0x3807e000,
1518
  0x38080000, 0x38082000, 0x38084000, 0x38086000, 0x38088000, 0x3808a000, 0x3808c000, 0x3808e000,
1519
  0x38090000, 0x38092000, 0x38094000, 0x38096000, 0x38098000, 0x3809a000, 0x3809c000, 0x3809e000,
1520
  0x380a0000, 0x380a2000, 0x380a4000, 0x380a6000, 0x380a8000, 0x380aa000, 0x380ac000, 0x380ae000,
1521
  0x380b0000, 0x380b2000, 0x380b4000, 0x380b6000, 0x380b8000, 0x380ba000, 0x380bc000, 0x380be000,
1522
  0x380c0000, 0x380c2000, 0x380c4000, 0x380c6000, 0x380c8000, 0x380ca000, 0x380cc000, 0x380ce000,
1523
  0x380d0000, 0x380d2000, 0x380d4000, 0x380d6000, 0x380d8000, 0x380da000, 0x380dc000, 0x380de000,
1524
  0x380e0000, 0x380e2000, 0x380e4000, 0x380e6000, 0x380e8000, 0x380ea000, 0x380ec000, 0x380ee000,
1525
  0x380f0000, 0x380f2000, 0x380f4000, 0x380f6000, 0x380f8000, 0x380fa000, 0x380fc000, 0x380fe000,
1526
  0x38100000, 0x38102000, 0x38104000, 0x38106000, 0x38108000, 0x3810a000, 0x3810c000, 0x3810e000,
1527
  0x38110000, 0x38112000, 0x38114000, 0x38116000, 0x38118000, 0x3811a000, 0x3811c000, 0x3811e000,
1528
  0x38120000, 0x38122000, 0x38124000, 0x38126000, 0x38128000, 0x3812a000, 0x3812c000, 0x3812e000,
1529
  0x38130000, 0x38132000, 0x38134000, 0x38136000, 0x38138000, 0x3813a000, 0x3813c000, 0x3813e000,
1530
  0x38140000, 0x38142000, 0x38144000, 0x38146000, 0x38148000, 0x3814a000, 0x3814c000, 0x3814e000,
1531
  0x38150000, 0x38152000, 0x38154000, 0x38156000, 0x38158000, 0x3815a000, 0x3815c000, 0x3815e000,
1532
  0x38160000, 0x38162000, 0x38164000, 0x38166000, 0x38168000, 0x3816a000, 0x3816c000, 0x3816e000,
1533
  0x38170000, 0x38172000, 0x38174000, 0x38176000, 0x38178000, 0x3817a000, 0x3817c000, 0x3817e000,
1534
  0x38180000, 0x38182000, 0x38184000, 0x38186000, 0x38188000, 0x3818a000, 0x3818c000, 0x3818e000,
1535
  0x38190000, 0x38192000, 0x38194000, 0x38196000, 0x38198000, 0x3819a000, 0x3819c000, 0x3819e000,
1536
  0x381a0000, 0x381a2000, 0x381a4000, 0x381a6000, 0x381a8000, 0x381aa000, 0x381ac000, 0x381ae000,
1537
  0x381b0000, 0x381b2000, 0x381b4000, 0x381b6000, 0x381b8000, 0x381ba000, 0x381bc000, 0x381be000,
1538
  0x381c0000, 0x381c2000, 0x381c4000, 0x381c6000, 0x381c8000, 0x381ca000, 0x381cc000, 0x381ce000,
1539
  0x381d0000, 0x381d2000, 0x381d4000, 0x381d6000, 0x381d8000, 0x381da000, 0x381dc000, 0x381de000,
1540
  0x381e0000, 0x381e2000, 0x381e4000, 0x381e6000, 0x381e8000, 0x381ea000, 0x381ec000, 0x381ee000,
1541
  0x381f0000, 0x381f2000, 0x381f4000, 0x381f6000, 0x381f8000, 0x381fa000, 0x381fc000, 0x381fe000,
1542
  0x38200000, 0x38202000, 0x38204000, 0x38206000, 0x38208000, 0x3820a000, 0x3820c000, 0x3820e000,
1543
  0x38210000, 0x38212000, 0x38214000, 0x38216000, 0x38218000, 0x3821a000, 0x3821c000, 0x3821e000,
1544
  0x38220000, 0x38222000, 0x38224000, 0x38226000, 0x38228000, 0x3822a000, 0x3822c000, 0x3822e000,
1545
  0x38230000, 0x38232000, 0x38234000, 0x38236000, 0x38238000, 0x3823a000, 0x3823c000, 0x3823e000,
1546
  0x38240000, 0x38242000, 0x38244000, 0x38246000, 0x38248000, 0x3824a000, 0x3824c000, 0x3824e000,
1547
  0x38250000, 0x38252000, 0x38254000, 0x38256000, 0x38258000, 0x3825a000, 0x3825c000, 0x3825e000,
1548
  0x38260000, 0x38262000, 0x38264000, 0x38266000, 0x38268000, 0x3826a000, 0x3826c000, 0x3826e000,
1549
  0x38270000, 0x38272000, 0x38274000, 0x38276000, 0x38278000, 0x3827a000, 0x3827c000, 0x3827e000,
1550
  0x38280000, 0x38282000, 0x38284000, 0x38286000, 0x38288000, 0x3828a000, 0x3828c000, 0x3828e000,
1551
  0x38290000, 0x38292000, 0x38294000, 0x38296000, 0x38298000, 0x3829a000, 0x3829c000, 0x3829e000,
1552
  0x382a0000, 0x382a2000, 0x382a4000, 0x382a6000, 0x382a8000, 0x382aa000, 0x382ac000, 0x382ae000,
1553
  0x382b0000, 0x382b2000, 0x382b4000, 0x382b6000, 0x382b8000, 0x382ba000, 0x382bc000, 0x382be000,
1554
  0x382c0000, 0x382c2000, 0x382c4000, 0x382c6000, 0x382c8000, 0x382ca000, 0x382cc000, 0x382ce000,
1555
  0x382d0000, 0x382d2000, 0x382d4000, 0x382d6000, 0x382d8000, 0x382da000, 0x382dc000, 0x382de000,
1556
  0x382e0000, 0x382e2000, 0x382e4000, 0x382e6000, 0x382e8000, 0x382ea000, 0x382ec000, 0x382ee000,
1557
  0x382f0000, 0x382f2000, 0x382f4000, 0x382f6000, 0x382f8000, 0x382fa000, 0x382fc000, 0x382fe000,
1558
  0x38300000, 0x38302000, 0x38304000, 0x38306000, 0x38308000, 0x3830a000, 0x3830c000, 0x3830e000,
1559
  0x38310000, 0x38312000, 0x38314000, 0x38316000, 0x38318000, 0x3831a000, 0x3831c000, 0x3831e000,
1560
  0x38320000, 0x38322000, 0x38324000, 0x38326000, 0x38328000, 0x3832a000, 0x3832c000, 0x3832e000,
1561
  0x38330000, 0x38332000, 0x38334000, 0x38336000, 0x38338000, 0x3833a000, 0x3833c000, 0x3833e000,
1562
  0x38340000, 0x38342000, 0x38344000, 0x38346000, 0x38348000, 0x3834a000, 0x3834c000, 0x3834e000,
1563
  0x38350000, 0x38352000, 0x38354000, 0x38356000, 0x38358000, 0x3835a000, 0x3835c000, 0x3835e000,
1564
  0x38360000, 0x38362000, 0x38364000, 0x38366000, 0x38368000, 0x3836a000, 0x3836c000, 0x3836e000,
1565
  0x38370000, 0x38372000, 0x38374000, 0x38376000, 0x38378000, 0x3837a000, 0x3837c000, 0x3837e000,
1566
  0x38380000, 0x38382000, 0x38384000, 0x38386000, 0x38388000, 0x3838a000, 0x3838c000, 0x3838e000,
1567
  0x38390000, 0x38392000, 0x38394000, 0x38396000, 0x38398000, 0x3839a000, 0x3839c000, 0x3839e000,
1568
  0x383a0000, 0x383a2000, 0x383a4000, 0x383a6000, 0x383a8000, 0x383aa000, 0x383ac000, 0x383ae000,
1569
  0x383b0000, 0x383b2000, 0x383b4000, 0x383b6000, 0x383b8000, 0x383ba000, 0x383bc000, 0x383be000,
1570
  0x383c0000, 0x383c2000, 0x383c4000, 0x383c6000, 0x383c8000, 0x383ca000, 0x383cc000, 0x383ce000,
1571
  0x383d0000, 0x383d2000, 0x383d4000, 0x383d6000, 0x383d8000, 0x383da000, 0x383dc000, 0x383de000,
1572
  0x383e0000, 0x383e2000, 0x383e4000, 0x383e6000, 0x383e8000, 0x383ea000, 0x383ec000, 0x383ee000,
1573
  0x383f0000, 0x383f2000, 0x383f4000, 0x383f6000, 0x383f8000, 0x383fa000, 0x383fc000, 0x383fe000,
1574
  0x38400000, 0x38402000, 0x38404000, 0x38406000, 0x38408000, 0x3840a000, 0x3840c000, 0x3840e000,
1575
  0x38410000, 0x38412000, 0x38414000, 0x38416000, 0x38418000, 0x3841a000, 0x3841c000, 0x3841e000,
1576
  0x38420000, 0x38422000, 0x38424000, 0x38426000, 0x38428000, 0x3842a000, 0x3842c000, 0x3842e000,
1577
  0x38430000, 0x38432000, 0x38434000, 0x38436000, 0x38438000, 0x3843a000, 0x3843c000, 0x3843e000,
1578
  0x38440000, 0x38442000, 0x38444000, 0x38446000, 0x38448000, 0x3844a000, 0x3844c000, 0x3844e000,
1579
  0x38450000, 0x38452000, 0x38454000, 0x38456000, 0x38458000, 0x3845a000, 0x3845c000, 0x3845e000,
1580
  0x38460000, 0x38462000, 0x38464000, 0x38466000, 0x38468000, 0x3846a000, 0x3846c000, 0x3846e000,
1581
  0x38470000, 0x38472000, 0x38474000, 0x38476000, 0x38478000, 0x3847a000, 0x3847c000, 0x3847e000,
1582
  0x38480000, 0x38482000, 0x38484000, 0x38486000, 0x38488000, 0x3848a000, 0x3848c000, 0x3848e000,
1583
  0x38490000, 0x38492000, 0x38494000, 0x38496000, 0x38498000, 0x3849a000, 0x3849c000, 0x3849e000,
1584
  0x384a0000, 0x384a2000, 0x384a4000, 0x384a6000, 0x384a8000, 0x384aa000, 0x384ac000, 0x384ae000,
1585
  0x384b0000, 0x384b2000, 0x384b4000, 0x384b6000, 0x384b8000, 0x384ba000, 0x384bc000, 0x384be000,
1586
  0x384c0000, 0x384c2000, 0x384c4000, 0x384c6000, 0x384c8000, 0x384ca000, 0x384cc000, 0x384ce000,
1587
  0x384d0000, 0x384d2000, 0x384d4000, 0x384d6000, 0x384d8000, 0x384da000, 0x384dc000, 0x384de000,
1588
  0x384e0000, 0x384e2000, 0x384e4000, 0x384e6000, 0x384e8000, 0x384ea000, 0x384ec000, 0x384ee000,
1589
  0x384f0000, 0x384f2000, 0x384f4000, 0x384f6000, 0x384f8000, 0x384fa000, 0x384fc000, 0x384fe000,
1590
  0x38500000, 0x38502000, 0x38504000, 0x38506000, 0x38508000, 0x3850a000, 0x3850c000, 0x3850e000,
1591
  0x38510000, 0x38512000, 0x38514000, 0x38516000, 0x38518000, 0x3851a000, 0x3851c000, 0x3851e000,
1592
  0x38520000, 0x38522000, 0x38524000, 0x38526000, 0x38528000, 0x3852a000, 0x3852c000, 0x3852e000,
1593
  0x38530000, 0x38532000, 0x38534000, 0x38536000, 0x38538000, 0x3853a000, 0x3853c000, 0x3853e000,
1594
  0x38540000, 0x38542000, 0x38544000, 0x38546000, 0x38548000, 0x3854a000, 0x3854c000, 0x3854e000,
1595
  0x38550000, 0x38552000, 0x38554000, 0x38556000, 0x38558000, 0x3855a000, 0x3855c000, 0x3855e000,
1596
  0x38560000, 0x38562000, 0x38564000, 0x38566000, 0x38568000, 0x3856a000, 0x3856c000, 0x3856e000,
1597
  0x38570000, 0x38572000, 0x38574000, 0x38576000, 0x38578000, 0x3857a000, 0x3857c000, 0x3857e000,
1598
  0x38580000, 0x38582000, 0x38584000, 0x38586000, 0x38588000, 0x3858a000, 0x3858c000, 0x3858e000,
1599
  0x38590000, 0x38592000, 0x38594000, 0x38596000, 0x38598000, 0x3859a000, 0x3859c000, 0x3859e000,
1600
  0x385a0000, 0x385a2000, 0x385a4000, 0x385a6000, 0x385a8000, 0x385aa000, 0x385ac000, 0x385ae000,
1601
  0x385b0000, 0x385b2000, 0x385b4000, 0x385b6000, 0x385b8000, 0x385ba000, 0x385bc000, 0x385be000,
1602
  0x385c0000, 0x385c2000, 0x385c4000, 0x385c6000, 0x385c8000, 0x385ca000, 0x385cc000, 0x385ce000,
1603
  0x385d0000, 0x385d2000, 0x385d4000, 0x385d6000, 0x385d8000, 0x385da000, 0x385dc000, 0x385de000,
1604
  0x385e0000, 0x385e2000, 0x385e4000, 0x385e6000, 0x385e8000, 0x385ea000, 0x385ec000, 0x385ee000,
1605
  0x385f0000, 0x385f2000, 0x385f4000, 0x385f6000, 0x385f8000, 0x385fa000, 0x385fc000, 0x385fe000,
1606
  0x38600000, 0x38602000, 0x38604000, 0x38606000, 0x38608000, 0x3860a000, 0x3860c000, 0x3860e000,
1607
  0x38610000, 0x38612000, 0x38614000, 0x38616000, 0x38618000, 0x3861a000, 0x3861c000, 0x3861e000,
1608
  0x38620000, 0x38622000, 0x38624000, 0x38626000, 0x38628000, 0x3862a000, 0x3862c000, 0x3862e000,
1609
  0x38630000, 0x38632000, 0x38634000, 0x38636000, 0x38638000, 0x3863a000, 0x3863c000, 0x3863e000,
1610
  0x38640000, 0x38642000, 0x38644000, 0x38646000, 0x38648000, 0x3864a000, 0x3864c000, 0x3864e000,
1611
  0x38650000, 0x38652000, 0x38654000, 0x38656000, 0x38658000, 0x3865a000, 0x3865c000, 0x3865e000,
1612
  0x38660000, 0x38662000, 0x38664000, 0x38666000, 0x38668000, 0x3866a000, 0x3866c000, 0x3866e000,
1613
  0x38670000, 0x38672000, 0x38674000, 0x38676000, 0x38678000, 0x3867a000, 0x3867c000, 0x3867e000,
1614
  0x38680000, 0x38682000, 0x38684000, 0x38686000, 0x38688000, 0x3868a000, 0x3868c000, 0x3868e000,
1615
  0x38690000, 0x38692000, 0x38694000, 0x38696000, 0x38698000, 0x3869a000, 0x3869c000, 0x3869e000,
1616
  0x386a0000, 0x386a2000, 0x386a4000, 0x386a6000, 0x386a8000, 0x386aa000, 0x386ac000, 0x386ae000,
1617
  0x386b0000, 0x386b2000, 0x386b4000, 0x386b6000, 0x386b8000, 0x386ba000, 0x386bc000, 0x386be000,
1618
  0x386c0000, 0x386c2000, 0x386c4000, 0x386c6000, 0x386c8000, 0x386ca000, 0x386cc000, 0x386ce000,
1619
  0x386d0000, 0x386d2000, 0x386d4000, 0x386d6000, 0x386d8000, 0x386da000, 0x386dc000, 0x386de000,
1620
  0x386e0000, 0x386e2000, 0x386e4000, 0x386e6000, 0x386e8000, 0x386ea000, 0x386ec000, 0x386ee000,
1621
  0x386f0000, 0x386f2000, 0x386f4000, 0x386f6000, 0x386f8000, 0x386fa000, 0x386fc000, 0x386fe000,
1622
  0x38700000, 0x38702000, 0x38704000, 0x38706000, 0x38708000, 0x3870a000, 0x3870c000, 0x3870e000,
1623
  0x38710000, 0x38712000, 0x38714000, 0x38716000, 0x38718000, 0x3871a000, 0x3871c000, 0x3871e000,
1624
  0x38720000, 0x38722000, 0x38724000, 0x38726000, 0x38728000, 0x3872a000, 0x3872c000, 0x3872e000,
1625
  0x38730000, 0x38732000, 0x38734000, 0x38736000, 0x38738000, 0x3873a000, 0x3873c000, 0x3873e000,
1626
  0x38740000, 0x38742000, 0x38744000, 0x38746000, 0x38748000, 0x3874a000, 0x3874c000, 0x3874e000,
1627
  0x38750000, 0x38752000, 0x38754000, 0x38756000, 0x38758000, 0x3875a000, 0x3875c000, 0x3875e000,
1628
  0x38760000, 0x38762000, 0x38764000, 0x38766000, 0x38768000, 0x3876a000, 0x3876c000, 0x3876e000,
1629
  0x38770000, 0x38772000, 0x38774000, 0x38776000, 0x38778000, 0x3877a000, 0x3877c000, 0x3877e000,
1630
  0x38780000, 0x38782000, 0x38784000, 0x38786000, 0x38788000, 0x3878a000, 0x3878c000, 0x3878e000,
1631
  0x38790000, 0x38792000, 0x38794000, 0x38796000, 0x38798000, 0x3879a000, 0x3879c000, 0x3879e000,
1632
  0x387a0000, 0x387a2000, 0x387a4000, 0x387a6000, 0x387a8000, 0x387aa000, 0x387ac000, 0x387ae000,
1633
  0x387b0000, 0x387b2000, 0x387b4000, 0x387b6000, 0x387b8000, 0x387ba000, 0x387bc000, 0x387be000,
1634
  0x387c0000, 0x387c2000, 0x387c4000, 0x387c6000, 0x387c8000, 0x387ca000, 0x387cc000, 0x387ce000,
1635
  0x387d0000, 0x387d2000, 0x387d4000, 0x387d6000, 0x387d8000, 0x387da000, 0x387dc000, 0x387de000,
1636
  0x387e0000, 0x387e2000, 0x387e4000, 0x387e6000, 0x387e8000, 0x387ea000, 0x387ec000, 0x387ee000,
1637
  0x387f0000, 0x387f2000, 0x387f4000, 0x387f6000, 0x387f8000, 0x387fa000, 0x387fc000, 0x387fe000,
1638
};
1639
1640
static uint32_t _ccv_exponent_table[64] = {
1641
  0x0, 0x800000, 0x1000000, 0x1800000, 0x2000000, 0x2800000, 0x3000000, 0x3800000,
1642
  0x4000000, 0x4800000, 0x5000000, 0x5800000, 0x6000000, 0x6800000, 0x7000000, 0x7800000,
1643
  0x8000000, 0x8800000, 0x9000000, 0x9800000, 0xa000000, 0xa800000, 0xb000000, 0xb800000,
1644
  0xc000000, 0xc800000, 0xd000000, 0xd800000, 0xe000000, 0xe800000, 0xf000000, 0x47800000,
1645
  0x80000000, 0x80800000, 0x81000000, 0x81800000, 0x82000000, 0x82800000, 0x83000000, 0x83800000,
1646
  0x84000000, 0x84800000, 0x85000000, 0x85800000, 0x86000000, 0x86800000, 0x87000000, 0x87800000,
1647
  0x88000000, 0x88800000, 0x89000000, 0x89800000, 0x8a000000, 0x8a800000, 0x8b000000, 0x8b800000,
1648
  0x8c000000, 0x8c800000, 0x8d000000, 0x8d800000, 0x8e000000, 0x8e800000, 0x8f000000, 0xc7800000,
1649
};
1650
1651
static uint16_t _ccv_offset_table[64] = {
1652
  0x0, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1653
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1654
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1655
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1656
  0x0, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1657
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1658
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1659
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1660
};
1661
1662
void ccv_half_precision_to_float(uint16_t* h, float* f, size_t len)
1663
19.7M
{
1664
19.7M
  int i;
1665
19.7M
  uint32_t* u = (uint32_t*)f;
1666
1.08G
  for (i = 0; i < len; 
i++1.06G
)
1667
1.06G
    u[i] = _ccv_mantissa_table[_ccv_offset_table[h[i] >> 10] + (h[i] & 0x3ff)] + _ccv_exponent_table[h[i] >> 10];
1668
19.7M
}
1669
1670
void ccv_half_precision_to_double(uint16_t* h, double* f, size_t len)
1671
0
{
1672
0
  int i;
1673
0
  for (i = 0; i < len; i++)
1674
0
  {
1675
0
    union {
1676
0
      float v;
1677
0
      uint32_t p;
1678
0
    } u = {
1679
0
      .p = _ccv_mantissa_table[_ccv_offset_table[h[i] >> 10] + (h[i] & 0x3ff)] + _ccv_exponent_table[h[i] >> 10]
1680
0
    };
1681
0
    f[i] = u.v;
1682
0
  }
1683
0
}
1684
1685
void ccv_array_push(ccv_array_t* array, const void* r)
1686
6.08M
{
1687
6.08M
  array->rnum++;
1688
6.08M
  if (array->rnum > array->size)
1689
138k
  {
1690
138k
    array->size = ccv_max(array->size * 3 / 2, array->size + 1);
1691
138k
    array->data = ccrealloc(array->data, (size_t)array->size * (size_t)array->rsize);
1692
138k
  }
1693
6.08M
  memcpy(ccv_array_get(array, array->rnum - 1), r, array->rsize);
1694
6.08M
}
1695
1696
void ccv_array_zero(ccv_array_t* array)
1697
69
{
1698
69
  memset(array->data, 0, (size_t)array->size * (size_t)array->rsize);
1699
69
}
1700
1701
void ccv_array_resize(ccv_array_t* array, int rnum)
1702
83.7k
{
1703
83.7k
  if (rnum > array->size)
1704
42.2k
  {
1705
42.2k
    array->size = ccv_max(array->size * 3 / 2, rnum);
1706
42.2k
    array->data = ccrealloc(array->data, (size_t)array->size * (size_t)array->rsize);
1707
42.2k
  }
1708
83.7k
  if (rnum > array->rnum)
1709
83.7k
    memset(ccv_array_get(array, array->rnum), 0, (size_t)array->rsize * (size_t)(rnum - array->rnum));
1710
83.7k
  array->rnum = rnum;
1711
83.7k
}
1712
1713
void ccv_array_clear(ccv_array_t* array)
1714
141k
{
1715
141k
  array->rnum = 0;
1716
141k
}
1717
1718
typedef struct ccv_ptree_node_t
1719
{
1720
  struct ccv_ptree_node_t* parent;
1721
  void* element;
1722
  int rank;
1723
} ccv_ptree_node_t;
1724
1725
/* the code for grouping array is adopted from OpenCV's cvSeqPartition func, it is essentially a find-union algorithm */
1726
int ccv_array_group(ccv_array_t* array, ccv_array_t** index, ccv_array_group_f gfunc, void* data)
1727
1
{
1728
1
  int i, j;
1729
1
  ccv_ptree_node_t* node = (ccv_ptree_node_t*)ccmalloc(array->rnum * sizeof(ccv_ptree_node_t));
1730
9
  for (i = 0; i < array->rnum; 
i++8
)
1731
8
  {
1732
8
    node[i].parent = 0;
1733
8
    node[i].element = ccv_array_get(array, i);
1734
8
    node[i].rank = 0;
1735
8
  }
1736
9
  for (i = 0; i < array->rnum; 
i++8
)
1737
8
  {
1738
8
    if (!node[i].element)
1739
0
      continue;
1740
8
    ccv_ptree_node_t* root = node + i;
1741
9
    while (root->parent)
1742
1
      root = root->parent;
1743
72
    for (j = 0; j < array->rnum; 
j++64
)
1744
64
    {
1745
64
      if( i != j && 
node[j].element56
&&
gfunc(node[i].element, node[j].element, data)56
)
1746
8
      {
1747
8
        ccv_ptree_node_t* root2 = node + j;
1748
8
1749
12
        while(root2->parent)
1750
4
          root2 = root2->parent;
1751
8
1752
8
        if(root2 != root)
1753
3
        {
1754
3
          if(root->rank > root2->rank)
1755
1
            root2->parent = root;
1756
2
          else
1757
2
          {
1758
2
            root->parent = root2;
1759
2
            root2->rank += root->rank == root2->rank;
1760
2
            root = root2;
1761
2
          }
1762
3
1763
3
          /* compress path from node2 to the root: */
1764
3
          ccv_ptree_node_t* node2 = node + j;
1765
4
          while(node2->parent)
1766
1
          {
1767
1
            ccv_ptree_node_t* temp = node2;
1768
1
            node2 = node2->parent;
1769
1
            temp->parent = root;
1770
1
          }
1771
3
1772
3
          /* compress path from node to the root: */
1773
3
          node2 = node + i;
1774
6
          while(node2->parent)
1775
3
          {
1776
3
            ccv_ptree_node_t* temp = node2;
1777
3
            node2 = node2->parent;
1778
3
            temp->parent = root;
1779
3
          }
1780
3
        }
1781
8
      }
1782
64
    }
1783
8
  }
1784
1
  if (*index == 0)
1785
1
    *index = ccv_array_new(sizeof(int), array->rnum, 0);
1786
0
  else
1787
0
    ccv_array_clear(*index);
1788
1
  ccv_array_t* idx = *index;
1789
1
1790
1
  int class_idx = 0;
1791
9
  for(i = 0; i < array->rnum; 
i++8
)
1792
8
  {
1793
8
    j = -1;
1794
8
    ccv_ptree_node_t* node1 = node + i;
1795
8
    if(node1->element)
1796
8
    {
1797
11
      while(node1->parent)
1798
3
        node1 = node1->parent;
1799
8
      if(node1->rank >= 0)
1800
5
        node1->rank = ~class_idx++;
1801
8
      j = ~node1->rank;
1802
8
    }
1803
8
    ccv_array_push(idx, &j);
1804
8
  }
1805
1
  ccfree(node);
1806
1
  return class_idx;
1807
1
}
1808
1809
ccv_contour_t* ccv_contour_new(int set)
1810
0
{
1811
0
  ccv_contour_t* contour = (ccv_contour_t*)ccmalloc(sizeof(ccv_contour_t));
1812
0
  contour->rect.x = contour->rect.y =
1813
0
  contour->rect.width = contour->rect.height = 0;
1814
0
  contour->size = 0;
1815
0
  if (set)
1816
0
    contour->set = ccv_array_new(sizeof(ccv_point_t), 5, 0);
1817
0
  else
1818
0
    contour->set = 0;
1819
0
  return contour;
1820
0
}
1821
1822
void ccv_contour_push(ccv_contour_t* contour, ccv_point_t point)
1823
0
{
1824
0
  if (contour->size == 0)
1825
0
  {
1826
0
    contour->rect.x = point.x;
1827
0
    contour->rect.y = point.y;
1828
0
    contour->rect.width = contour->rect.height = 1;
1829
0
    contour->m10 = point.x;
1830
0
    contour->m01 = point.y;
1831
0
    contour->m11 = point.x * point.y;
1832
0
    contour->m20 = point.x * point.x;
1833
0
    contour->m02 = point.y * point.y;
1834
0
    contour->size = 1;
1835
0
  } else {
1836
0
    if (point.x < contour->rect.x)
1837
0
    {
1838
0
      contour->rect.width += contour->rect.x - point.x;
1839
0
      contour->rect.x = point.x;
1840
0
    } else if (point.x > contour->rect.x + contour->rect.width - 1) {
1841
0
      contour->rect.width = point.x - contour->rect.x + 1;
1842
0
    }
1843
0
    if (point.y < contour->rect.y)
1844
0
    {
1845
0
      contour->rect.height += contour->rect.y - point.y;
1846
0
      contour->rect.y = point.y;
1847
0
    } else if (point.y > contour->rect.y + contour->rect.height - 1) {
1848
0
      contour->rect.height = point.y - contour->rect.y + 1;
1849
0
    }
1850
0
    contour->m10 += point.x;
1851
0
    contour->m01 += point.y;
1852
0
    contour->m11 += point.x * point.y;
1853
0
    contour->m20 += point.x * point.x;
1854
0
    contour->m02 += point.y * point.y;
1855
0
    contour->size++;
1856
0
  }
1857
0
  if (contour->set)
1858
0
    ccv_array_push(contour->set, &point);
1859
0
}
1860
1861
void ccv_contour_free(ccv_contour_t* contour)
1862
0
{
1863
0
  if (contour->set)
1864
0
    ccv_array_free(contour->set);
1865
0
  ccfree(contour);
1866
0
}