Coverage Report

Created: 2019-07-03 22:50

/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
7.00M
{
6
7.00M
  int type = *(int*)mat;
7
7.00M
  if (type & CCV_MATRIX_DENSE)
8
7.00M
    return (ccv_dense_matrix_t*)mat;
9
1.10k
  return 0;
10
1.10k
}
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, 0)); \
42
0
      maxval = ccv_max(maxval, _for_get(aptr, j, 0)); \
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, 0) - 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
3.48M
{
68
3.48M
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
69
3.48M
  assert((da->type & CCV_32F) || (da->type & CCV_64F));
70
3.48M
  
int ch = 3.46M
CCV_GET_CHANNEL3.46M
(da->type);
71
3.46M
  int i;
72
3.46M
  if (da->type & CCV_32F)
73
3.46M
  {
74
2.14G
    for (i = 0; i < da->rows * da->cols * ch; 
i++2.13G
)
75
#ifdef isnanf
76
      if (isnanf(da->data.f32[i]))
77
#else
78
2.13G
      if (isnan(da->data.f32[i]))
79
2.13G
#endif
80
2.13G
        
return i + 10
;
81
3.46M
  } else {
82
144
    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
144
  }
86
3.46M
  return 0;
87
3.46M
}
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_get(aptr, j * ch + k, 0); \
108
4
      _for_set(bptr, j, sum, 0); \
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, 0), 0); \
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
0
{
157
0
  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
158
0
  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
0
  type = (type == 0) ? CCV_GET_DATA_TYPE(da->type) | CCV_GET_CHANNEL(da->type) : CCV_GET_DATA_TYPE(type) | CCV_GET_CHANNEL(da->type);
160
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), type, sig); 
161
0
  ccv_object_return_if_cached(, db);
162
0
  int i, j, ch = CCV_GET_CHANNEL(da->type);
163
0
  unsigned char* aptr = da->data.u8;
164
0
  unsigned char* bptr = db->data.u8;
165
0
#define for_block(_for_get, _for_set) \
166
0
  for (i = 0; i < da->rows; i++) \
167
0
  { \
168
0
    for (j = 0; j < da->cols * ch; j++) \
169
0
    { \
170
0
      _for_set(bptr, j, _for_get(aptr, j, lr), rr); \
171
0
    } \
172
0
    aptr += da->step; \
173
0
    bptr += db->step; \
174
0
  }
175
0
  ccv_matrix_getter(da->type, ccv_matrix_setter, db->type, for_block);
176
0
#undef for_block
177
0
}
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
208M
{
182
208M
  switch(prime_index)
183
208M
  {
184
208M
  case 0:
185
0
    return 0u;
186
208M
  case 1:
187
148k
    return hash % 2u;
188
208M
  case 2:
189
0
    return hash % 3u;
190
208M
  case 3:
191
306k
    return hash % 5u;
192
208M
  case 4:
193
0
    return hash % 7u;
194
208M
  case 5:
195
278k
    return hash % 11u;
196
208M
  case 6:
197
0
    return hash % 13u;
198
208M
  case 7:
199
0
    return hash % 17u;
200
208M
  case 8:
201
235k
    return hash % 23u;
202
208M
  case 9:
203
0
    return hash % 29u;
204
208M
  case 10:
205
0
    return hash % 37u;
206
208M
  case 11:
207
416k
    return hash % 47u;
208
208M
  case 12:
209
0
    return hash % 59u;
210
208M
  case 13:
211
0
    return hash % 73u;
212
208M
  case 14:
213
532k
    return hash % 97u;
214
208M
  case 15:
215
0
    return hash % 127u;
216
208M
  case 16:
217
0
    return hash % 151u;
218
208M
  case 17:
219
768k
    return hash % 197u;
220
208M
  case 18:
221
0
    return hash % 251u;
222
208M
  case 19:
223
0
    return hash % 313u;
224
208M
  case 20:
225
1.58M
    return hash % 397u;
226
208M
  case 21:
227
0
    return hash % 499u;
228
208M
  case 22:
229
0
    return hash % 631u;
230
208M
  case 23:
231
2.93M
    return hash % 797u;
232
208M
  case 24:
233
0
    return hash % 1009u;
234
208M
  case 25:
235
0
    return hash % 1259u;
236
208M
  case 26:
237
201M
    return hash % 1597u;
238
208M
  case 27:
239
0
    return hash % 2011u;
240
208M
  case 28:
241
0
    return hash % 2539u;
242
208M
  case 29:
243
0
    return hash % 3203u;
244
208M
  case 30:
245
0
    return hash % 4027u;
246
208M
  case 31:
247
0
    return hash % 5087u;
248
208M
  case 32:
249
0
    return hash % 6421u;
250
208M
  case 33:
251
0
    return hash % 8089u;
252
208M
  case 34:
253
0
    return hash % 10193u;
254
208M
  case 35:
255
0
    return hash % 12853u;
256
208M
  case 36:
257
0
    return hash % 16193u;
258
208M
  case 37:
259
0
    return hash % 20399u;
260
208M
  case 38:
261
0
    return hash % 25717u;
262
208M
  case 39:
263
0
    return hash % 32401u;
264
208M
  case 40:
265
0
    return hash % 40823u;
266
208M
  case 41:
267
0
    return hash % 51437u;
268
208M
  case 42:
269
0
    return hash % 64811u;
270
208M
  case 43:
271
0
    return hash % 81649u;
272
208M
  case 44:
273
0
    return hash % 102877u;
274
208M
  case 45:
275
0
    return hash % 129607u;
276
208M
  case 46:
277
0
    return hash % 163307u;
278
208M
  case 47:
279
0
    return hash % 205759u;
280
208M
  case 48:
281
0
    return hash % 259229u;
282
208M
  case 49:
283
0
    return hash % 326617u;
284
208M
  case 50:
285
0
    return hash % 411527u;
286
208M
  case 51:
287
0
    return hash % 518509u;
288
208M
  case 52:
289
0
    return hash % 653267u;
290
208M
  case 53:
291
0
    return hash % 823117u;
292
208M
  case 54:
293
0
    return hash % 1037059u;
294
208M
  case 55:
295
0
    return hash % 1306601u;
296
208M
  case 56:
297
0
    return hash % 1646237u;
298
208M
  case 57:
299
0
    return hash % 2074129u;
300
208M
  case 58:
301
0
    return hash % 2613229u;
302
208M
  case 59:
303
0
    return hash % 3292489u;
304
208M
  case 60:
305
0
    return hash % 4148279u;
306
208M
  case 61:
307
0
    return hash % 5226491u;
308
208M
  case 62:
309
0
    return hash % 6584983u;
310
208M
  case 63:
311
0
    return hash % 8296553u;
312
208M
  case 64:
313
0
    return hash % 10453007u;
314
208M
  case 65:
315
0
    return hash % 13169977u;
316
208M
  case 66:
317
0
    return hash % 16593127u;
318
208M
  case 67:
319
0
    return hash % 20906033u;
320
208M
  case 68:
321
0
    return hash % 26339969u;
322
208M
  case 69:
323
0
    return hash % 33186281u;
324
208M
  case 70:
325
0
    return hash % 41812097u;
326
208M
  case 71:
327
0
    return hash % 52679969u;
328
208M
  case 72:
329
0
    return hash % 66372617u;
330
208M
  case 73:
331
0
    return hash % 83624237u;
332
208M
  case 74:
333
0
    return hash % 105359939u;
334
208M
  case 75:
335
0
    return hash % 132745199u;
336
208M
  case 76:
337
0
    return hash % 167248483u;
338
208M
  case 77:
339
0
    return hash % 210719881u;
340
208M
  case 78:
341
0
    return hash % 265490441u;
342
208M
  case 79:
343
0
    return hash % 334496971u;
344
208M
  case 80:
345
0
    return hash % 421439783u;
346
208M
  case 81:
347
0
    return hash % 530980861u;
348
208M
  case 82:
349
0
    return hash % 668993977u;
350
208M
  case 83:
351
0
    return hash % 842879579u;
352
208M
  case 84:
353
0
    return hash % 1061961721u;
354
208M
  case 85:
355
0
    return hash % 1337987929u;
356
208M
  case 86:
357
0
    return hash % 1685759167u;
358
208M
  case 87:
359
0
    return hash % 2123923447u;
360
208M
  case 88:
361
0
    return hash % 2675975881u;
362
208M
  case 89:
363
0
    return hash % 3371518343u;
364
208M
  case 90:
365
0
    return hash % 4247846927u;
366
208M
  case 91:
367
0
    return hash % 4294967291u;
368
208M
  default:
369
0
    return hash;
370
208M
  }
371
208M
}
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
55.0k
{
400
55.0k
  int i;
401
55.0k
  assert(sizeof(_ccv_sparse_prime) / sizeof(uint32_t) == 91);
402
389k
  
for (i = 0; 55.0k
i < sizeof(_ccv_sparse_prime) / sizeof(uint32_t);
i++334k
)
403
389k
    if (_ccv_sparse_prime[i] > size)
404
55.0k
      return i + 1;
405
55.0k
  
return sizeof(_ccv_sparse_prime) / sizeof(uint32_t) + 10
;
406
55.0k
}
407
408
static uint32_t _ccv_sparse_matrix_size_for_index(const int prime_index)
409
55.0k
{
410
55.0k
  return _ccv_sparse_prime[prime_index - 1];
411
55.0k
}
412
413
static void _ccv_init_sparse_matrix_vector(ccv_sparse_matrix_vector_t* vector, const ccv_sparse_matrix_t* const mat)
414
33.0k
{
415
33.0k
  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
32.8k
  vector->prime_index = 1; // See ccv_util.c to know why this is 1 and why size is 2.
424
32.8k
  vector->size = 2;
425
32.8k
  vector->rnum = 0;
426
32.8k
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
427
32.8k
  vector->index = (ccv_sparse_matrix_index_t*)cccalloc(sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned, vector->size);
428
32.8k
}
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
4.23k
{
432
4.23k
  uint32_t old_i = index[idx].i;
433
4.23k
  index[idx].i = i;
434
4.23k
  i = old_i;
435
4.23k
  ccv_sparse_matrix_vector_t val = vector[idx];
436
4.23k
  _ccv_init_sparse_matrix_vector(vector + idx, mat);
437
4.23k
  // Move to next idx, this is already occupied.
438
4.23k
  ++k;
439
4.23k
  ++idx;
440
41.3k
  for (; k < 255; 
++idx, ++k37.1k
)
441
41.3k
  {
442
41.3k
    if (idx >= size)
443
1.03k
      idx = 0;
444
41.3k
    if (!index[idx].ifbit)
445
4.23k
    {
446
4.23k
      index[idx].ifbit = k;
447
4.23k
      index[idx].i = i;
448
4.23k
      vector[idx] = val;
449
4.23k
      return;
450
4.23k
    }
451
37.1k
    uint32_t j = index[idx].ifbit;
452
37.1k
    if (k > j)
453
30.4k
    {
454
30.4k
      index[idx].ifbit = k;
455
30.4k
      k = j;
456
30.4k
      uint32_t old_i = index[idx].i;
457
30.4k
      index[idx].i = i;
458
30.4k
      i = old_i;
459
30.4k
      ccv_sparse_matrix_vector_t old_val = vector[idx];
460
30.4k
      vector[idx] = val;
461
30.4k
      val = old_val;
462
30.4k
    }
463
37.1k
  }
464
4.23k
  
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.51M
{
494
1.51M
  const uint32_t size = mat->size;
495
1.51M
  ccv_sparse_matrix_index_t* const index = mat->index;
496
1.51M
  ccv_sparse_matrix_vector_t* const vector = mat->vector;
497
1.51M
  const int prime_index = mat->prime_index;
498
1.51M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(i, prime_index);
499
1.51M
  uint32_t k = 2;
500
2.30M
  for (; k < 255; 
++idx, ++k790k
)
501
2.30M
  {
502
2.30M
    if (idx >= size)
503
655
      idx = 0;
504
2.30M
    uint32_t j = index[idx].ifbit;
505
2.30M
    if (k > j)
506
33.0k
    {
507
33.0k
      ++mat->rnum;
508
33.0k
      index[idx].ifbit = k;
509
33.0k
      if (!j)
510
28.7k
      {
511
28.7k
        index[idx].i = i;
512
28.7k
        _ccv_init_sparse_matrix_vector(vector + idx, mat);
513
28.7k
      } else
514
4.23k
        _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
33.0k
      return vector + idx;
516
33.0k
    }
517
2.27M
    if (index[idx].i == i)
518
1.47M
      return vector + idx;
519
2.27M
  }
520
1.51M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
521
1.51M
  
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
101M
{
548
101M
  const uint32_t size = mat->size;
549
101M
  ccv_sparse_matrix_index_t* index = mat->index;
550
101M
  ccv_sparse_matrix_vector_t* vector = mat->vector;
551
101M
  const int prime_index = mat->prime_index;
552
101M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(i, prime_index);
553
101M
  uint32_t k = 2;
554
104M
  for (; k < 255; 
++idx, ++k3.02M
)
555
104M
  {
556
104M
    if (idx >= size)
557
6.19k
      idx = 0;
558
104M
    if (k > index[idx].ifbit)
559
174k
      return 0;
560
104M
    if (index[idx].i == i)
561
101M
      return vector + idx;
562
104M
  }
563
101M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
564
101M
  
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
101M
{
581
101M
  ccv_numeric_data_t cell = {}; // zero-init.
582
101M
  const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);
583
101M
  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
101M
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
589
101M
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
590
101M
  const uint32_t size = vector->size;
591
101M
  uint8_t* const index = (uint8_t*)vector->index;
592
101M
  const int prime_index = vector->prime_index;
593
101M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(vidx, prime_index);
594
101M
  uint32_t k = 2;
595
105M
  for (; k < 255; 
++idx, ++k3.56M
)
596
105M
  {
597
105M
    if (idx >= size)
598
38.9k
      idx = 0;
599
105M
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
600
105M
    if (k > index_idx->ifbit)
601
652k
      return cell;
602
104M
    if (index_idx->i == vidx)
603
100M
    {
604
100M
      cell.u8 = (uint8_t*)(index_idx + 1);
605
100M
      return cell;
606
100M
    }
607
104M
  }
608
101M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
609
101M
  
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
101M
{
629
101M
  ccv_sparse_matrix_vector_t* vector = ccv_get_sparse_matrix_vector(mat, (mat->major == CCV_SPARSE_COL_MAJOR) ? 
col0
: row);
630
101M
  if (!vector || 
!vector->rnum101M
)
631
149k
    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
45.8k
{
638
45.8k
  assert(vector->prime_index >= 0 && vector->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
639
45.8k
  const uint32_t size = vector->size;
640
45.8k
  const int prime_index = vector->prime_index = _ccv_sparse_matrix_index_next_size_over(size * 2);
641
45.8k
  const uint32_t new_size = vector->size = _ccv_sparse_matrix_size_for_index(vector->prime_index);
642
45.8k
  assert(vector->prime_index >= 0 && vector->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
643
45.8k
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
644
45.8k
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
645
45.8k
  const size_t cell_rnum = cell_size_aligned / sizeof(uint32_t);
646
45.8k
  vector->index = (ccv_sparse_matrix_index_t*)ccrealloc(vector->index, index_size * new_size);
647
45.8k
  uint8_t* const index = (uint8_t*)vector->index;
648
45.8k
  memset(index + index_size * size, 0, index_size * (new_size - size));
649
45.8k
  uint32_t i, h;
650
2.28M
  for (i = 0; i < size; 
i++2.23M
)
651
2.23M
  {
652
2.23M
    ccv_sparse_matrix_index_t* index_i = (ccv_sparse_matrix_index_t*)(index + index_size * i);
653
2.23M
    index_i->ifbit = !!index_i->ifbit; // Mark this as need to be moved around.
654
2.23M
  }
655
2.28M
  for (i = 0; i < size; 
i++2.23M
)
656
2.23M
  {
657
2.23M
    ccv_sparse_matrix_index_t* index_i = (ccv_sparse_matrix_index_t*)(index + index_size * i);
658
2.23M
    if (index_i->ifbit == 1) // Encountered one need to be moved.
659
1.93M
    {
660
1.93M
      index_i->ifbit = 0;
661
1.93M
      // This item is from old hash table, need to find a new location for it.
662
1.93M
      uint32_t key = index_i->i;
663
1.93M
      uint32_t* val = (uint32_t*)(index_i + 1);
664
1.93M
      uint32_t k = 2;
665
1.93M
      uint32_t idx = _ccv_sparse_matrix_index_for_hash(key, prime_index);
666
2.19M
      for (; k < 255; 
++idx, ++k260k
)
667
2.19M
      {
668
2.19M
        if (idx >= new_size)
669
476
          idx = 0;
670
2.19M
        ccv_sparse_matrix_index_t* index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
671
2.19M
        uint32_t j = index_idx->ifbit;
672
2.19M
        if (!j)
673
1.93M
        {
674
1.93M
          index_idx->ifbit = k;
675
1.93M
          index_idx->i = key;
676
1.93M
          memcpy(index_idx + 1, val, cell_size_aligned);
677
1.93M
          break;
678
1.93M
        }
679
260k
        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.
680
168k
          continue;
681
91.8k
        index_idx->ifbit = k;
682
91.8k
        uint32_t old_key = index_idx->i;
683
91.8k
        index_idx->i = key;
684
91.8k
        key = old_key;
685
91.8k
        uint32_t* old_val = (uint32_t*)(index_idx + 1);
686
184k
        for (h = 0; h < cell_rnum; 
h++92.5k
)
687
92.5k
        {
688
92.5k
          uint32_t v = old_val[h];
689
92.5k
          old_val[h] = val[h];
690
92.5k
          val[h] = v;
691
92.5k
        }
692
91.8k
        if (j != 1)
693
42.0k
          k = j;
694
49.8k
        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.
695
49.8k
          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;
696
49.8k
          k = 1; // Restart.
697
49.8k
        }
698
91.8k
      }
699
1.93M
      if (k < 255)
700
1.93M
        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.23M
  }
738
45.8k
}
739
740
static void _ccv_sparse_matrix_inc_size(ccv_sparse_matrix_t* mat)
741
9.13k
{
742
9.13k
  assert(mat->prime_index >= 0 && mat->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
743
9.13k
  const uint32_t size = mat->size;
744
9.13k
  const int prime_index = mat->prime_index = _ccv_sparse_matrix_index_next_size_over(size * 2);
745
9.13k
  const uint32_t new_size = mat->size = _ccv_sparse_matrix_size_for_index(mat->prime_index);
746
9.13k
  assert(mat->prime_index >= 0 && mat->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));
747
9.13k
  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
9.13k
  memset(index + size, 0, sizeof(ccv_sparse_matrix_index_t) * (new_size - size));
749
9.13k
  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
9.13k
  uint32_t i;
751
49.6k
  for (i = 0; i < size; 
i++40.5k
)
752
40.5k
    index[i].ifbit = !!index[i].ifbit; // Mark this as need to be moved around.
753
49.6k
  for (i = 0; i < size; 
i++40.5k
)
754
40.5k
    if (index[i].ifbit == 1) // Encountered one need to be moved.
755
29.8k
    {
756
29.8k
      index[i].ifbit = 0;
757
29.8k
      // This item is from old hash table, need to find a new location for it.
758
29.8k
      uint32_t key = index[i].i;
759
29.8k
      ccv_sparse_matrix_vector_t val = vector[i];
760
29.8k
      uint32_t k = 2;
761
29.8k
      uint32_t idx = _ccv_sparse_matrix_index_for_hash(key, prime_index);
762
35.0k
      for (; k < 255; 
++idx, ++k5.10k
)
763
35.0k
      {
764
35.0k
        if (idx >= new_size)
765
2
          idx = 0;
766
35.0k
        uint32_t j = index[idx].ifbit;
767
35.0k
        if (!j)
768
29.8k
        {
769
29.8k
          index[idx].ifbit = k;
770
29.8k
          index[idx].i = key;
771
29.8k
          vector[idx] = val;
772
29.8k
          break;
773
29.8k
        }
774
5.10k
        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.
775
4.17k
          continue;
776
932
        index[idx].ifbit = k;
777
932
        uint32_t old_key = index[idx].i;
778
932
        index[idx].i = key;
779
932
        key = old_key;
780
932
        ccv_sparse_matrix_vector_t old_val = vector[idx];
781
932
        vector[idx] = val;
782
932
        val = old_val;
783
932
        if (j != 1)
784
660
          k = j;
785
272
        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.
786
272
          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;
787
272
          k = 1; // Restart.
788
272
        }
789
932
      }
790
29.8k
      if (k < 255)
791
29.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
9.13k
}
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
137k
{
827
137k
  ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
828
137k
  const size_t cell_rnum = cell_size_aligned / sizeof(uint32_t);
829
137k
  uint32_t* val = (uint32_t*)(index_idx + 1);
830
137k
  uint32_t old_i = index_idx->i;
831
137k
  index_idx->i = i;
832
137k
  i = old_i;
833
137k
  // Move to next idx, this is already occupied.
834
137k
  ++k;
835
137k
  ++idx;
836
137k
  uint32_t h;
837
1.71M
  for (; k < 255; 
++idx, ++k1.57M
)
838
1.71M
  {
839
1.71M
    if (idx >= size)
840
7.79k
      idx = 0;
841
1.71M
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
842
1.71M
    if (!index_idx->ifbit)
843
137k
    {
844
137k
      index_idx->ifbit = k;
845
137k
      index_idx->i = i;
846
137k
      memcpy(index_idx + 1, val, cell_size_aligned);
847
137k
      return;
848
137k
    }
849
1.57M
    uint32_t j = index_idx->ifbit;
850
1.57M
    if (k > j)
851
1.39M
    {
852
1.39M
      index_idx->ifbit = k;
853
1.39M
      k = j;
854
1.39M
      uint32_t old_i = index_idx->i;
855
1.39M
      index_idx->i = i;
856
1.39M
      i = old_i;
857
1.39M
      uint32_t* old_val = (uint32_t*)(index_idx + 1);
858
2.80M
      for (h = 0; h < cell_rnum; 
h++1.40M
)
859
1.40M
      {
860
1.40M
        uint32_t v = old_val[h];
861
1.40M
        old_val[h] = val[h];
862
1.40M
        val[h] = v;
863
1.40M
      }
864
1.39M
    }
865
1.57M
  }
866
137k
  
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.51M
{
901
1.51M
  assert(data);
902
1.51M
  const int hidx = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
col200
:
row1.51M
;
903
1.51M
  const int vidx = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
row200
:
col1.51M
;
904
1.51M
  // This will handle initialize a vector if it doesn't already exist.
905
1.51M
  if ((mat->rnum + 1) * 10llu > mat->size * 9llu) // expand when reached 90%.
906
9.13k
    _ccv_sparse_matrix_inc_size(mat);
907
1.51M
  ccv_sparse_matrix_vector_t* const vector = _ccv_get_or_add_sparse_matrix_vector(mat, hidx);
908
1.51M
  const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);
909
1.51M
  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.51M
  if ((vector->rnum + 1) * 10llu > vector->size * 9llu) // expand when reached 90%.
915
45.8k
    _ccv_sparse_matrix_vector_inc_size(mat, vector);
916
1.51M
  // Align to 4 bytes.
917
1.51M
  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;
918
1.51M
  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;
919
1.51M
  uint8_t* const index = (uint8_t*)vector->index;
920
1.51M
  const int prime_index = vector->prime_index;
921
1.51M
  const uint32_t size = vector->size;
922
1.51M
  uint32_t idx = _ccv_sparse_matrix_index_for_hash(vidx, prime_index);
923
1.51M
  uint32_t k = 2;
924
2.84M
  for (; k < 255; 
++idx, ++k1.32M
)
925
2.84M
  {
926
2.84M
    if (idx >= size)
927
4.99k
      idx = 0;
928
2.84M
    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);
929
2.84M
    uint32_t j = index_idx->ifbit;
930
2.84M
    if (k > j)
931
1.44M
    {
932
1.44M
      ++vector->rnum;
933
1.44M
      index_idx->ifbit = k;
934
1.44M
      if (!j)
935
1.30M
      {
936
1.30M
        index_idx->i = vidx;
937
1.30M
        // Assign it out.
938
1.30M
        memcpy(index_idx + 1, data, cell_size);
939
1.30M
      } else {
940
137k
        _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
137k
        memcpy(index_idx + 1, data, cell_size);
942
137k
      }
943
1.44M
      return;
944
1.44M
    }
945
1.39M
    if (index_idx->i == vidx)
946
65.2k
    {
947
65.2k
      memcpy(index_idx + 1, data, cell_size);
948
65.2k
      return;
949
65.2k
    }
950
1.39M
  }
951
1.51M
  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.
952
1.51M
  
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, 0), 0); \
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, 0), 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
3
          case CCV_8U:
1086
0
            _ccv_indice_uchar_sort(idx, vector->rnum, (unsigned char*)m_ptr);
1087
0
            break;
1088
3
          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
3
          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
91
{
1120
91
  int a_type = *(int*)a;
1121
91
  int b_type = *(int*)b;
1122
91
  if ((a_type & CCV_MATRIX_DENSE) && (b_type & CCV_MATRIX_DENSE))
1123
91
  {
1124
91
    ccv_dense_matrix_t* da = (ccv_dense_matrix_t*)a;
1125
91
    ccv_dense_matrix_t* db = (ccv_dense_matrix_t*)b;
1126
91
    if (CCV_GET_DATA_TYPE(da->type) != CCV_GET_DATA_TYPE(db->type))
1127
91
      
return -10
;
1128
91
    if (CCV_GET_CHANNEL(da->type) != CCV_GET_CHANNEL(db->type))
1129
91
      
return -10
;
1130
91
    if (da->rows != db->rows)
1131
0
      return -1;
1132
91
    if (da->cols != db->cols)
1133
0
      return -1;
1134
91
    int i, j, ch = CCV_GET_CHANNEL(da->type);
1135
91
    unsigned char* a_ptr = da->data.u8;
1136
91
    unsigned char* b_ptr = db->data.u8;
1137
91
    // Read: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
1138
91
    // http://floating-point-gui.de/errors/comparison/
1139
91
    if (CCV_GET_DATA_TYPE(db->type) == CCV_32F)
1140
65
    {
1141
65
      static const float epsi = FLT_EPSILON;
1142
65
      static const int32_t ulps = 128; // So that for 1 and 1.000015 will be treated as the same.
1143
8.32k
      for (i = 0; i < da->rows; 
i++8.25k
)
1144
8.25k
      {
1145
8.25k
        int32_t* ia_ptr = (int32_t*)a_ptr;
1146
8.25k
        int32_t* ib_ptr = (int32_t*)b_ptr;
1147
12.6M
        for (j = 0; j < da->cols * ch; 
j++12.6M
)
1148
12.6M
        {
1149
12.6M
          int32_t i32a = ia_ptr[j];
1150
12.6M
          if (i32a < 0)
1151
6.34k
            i32a = 0x80000000 - i32a;
1152
12.6M
          int32_t i32b = ib_ptr[j];
1153
12.6M
          if (i32b < 0)
1154
6.34k
            i32b = 0x80000000 - i32b;
1155
12.6M
          if (abs(i32a - i32b) > ulps && 
fabsf(((float*)a_ptr)[j] - ((float*)b_ptr)[j]) > epsi0
)
1156
0
            return -1;
1157
12.6M
        }
1158
8.25k
        a_ptr += da->step;
1159
8.25k
        b_ptr += db->step;
1160
8.25k
      }
1161
65
    } else 
if (26
CCV_GET_DATA_TYPE26
(db->type) == CCV_64F26
) {
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
25
    } else {
1183
25
#define for_block(_, _for_get) \
1184
13.4k
      
for (i = 0; 25
i < da->rows;
i++13.4k
) \
1185
13.4k
      { \
1186
29.7M
        for (j = 0; j < da->cols * ch; 
j++29.7M
) \
1187
29.7M
        { \
1188
29.7M
          if (llabs(_for_get(b_ptr, j, 0) - _for_get(a_ptr, j, 0)) > 1) \
1189
29.7M
            
return -10
; \
1190
29.7M
        } \
1191
13.4k
        a_ptr += da->step; \
1192
13.4k
        b_ptr += db->step; \
1193
13.4k
      }
1194
25
      ccv_matrix_getter_integer_only(da->type, for_block);
1195
25
#undef for_block
1196
25
    }
1197
91
  }
1198
91
  return 0;
1199
91
}
1200
1201
void ccv_slice(ccv_matrix_t* a, ccv_matrix_t** b, int btype, int y, int x, int rows, int cols)
1202
3.49M
{
1203
3.49M
  int type = *(int*)a;
1204
3.49M
  if (type & CCV_MATRIX_DENSE)
1205
3.48M
  {
1206
3.48M
    ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
1207
3.48M
    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);
1208
3.48M
    btype = (btype == 0) ? 
CCV_GET_DATA_TYPE3.46M
(da->type) | 3.46M
CCV_GET_CHANNEL3.46M
(da->type) :
CCV_GET_DATA_TYPE12.6k
(btype) | 12.6k
CCV_GET_CHANNEL12.6k
(da->type);
1209
3.48M
    ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, rows, cols, CCV_ALL_DATA_TYPE | CCV_GET_CHANNEL(da->type), btype, sig);
1210
3.48M
    ccv_object_return_if_cached(, db);
1211
3.48M
    int i, j, ch = CCV_GET_CHANNEL(da->type);
1212
3.48M
    int dx = 0, dy = 0;
1213
3.48M
    if (!(y >= 0 && 
y + rows <= da->rows3.46M
&&
x >= 03.46M
&&
x + cols <= da->cols3.46M
))
1214
1
    {
1215
1
      ccv_zero(db);
1216
1
      if (y < 0) { rows += y; dy = -y; y = 0; }
1217
1
      if (y + rows > da->rows) rows = da->rows - y;
1218
1
      if (x < 0) 
{ cols += x; dx = -x; x = 0; }0
1219
1
      if (x + cols > da->cols) 
cols = da->cols - x0
;
1220
1
    }
1221
3.48M
    unsigned char* a_ptr = da->data.u8 + x * ch * CCV_GET_DATA_TYPE_SIZE(da->type) + y * da->step;
1222
3.48M
    unsigned char* b_ptr = db->data.u8 + dx * ch * CCV_GET_DATA_TYPE_SIZE(db->type) + dy * db->step;
1223
3.48M
#define for_block(_for_set, _for_get) \
1224
93.6M
    
for (i = 0; 3.43M
i < rows;
i++90.2M
) \
1225
90.2M
    { \
1226
2.50G
      for (j = 0; j < cols * ch; 
j++2.41G
) \
1227
2.41G
      { \
1228
2.41G
        _for_set(b_ptr, j, _for_get(a_ptr, j, 0), 0); \
1229
2.41G
      } \
1230
90.2M
      a_ptr += da->step; \
1231
90.2M
      b_ptr += db->step; \
1232
90.2M
    }
1233
3.48M
    ccv_matrix_setter(db->type, 
ccv_matrix_getter3.43M
, da->type,
for_block3.43M
);
1234
3.46M
#undef for_block
1235
3.46M
  } else 
if (10.5k
type & CCV_MATRIX_SPARSE10.5k
) {
1236
0
  }
1237
3.49M
}
1238
1239
ccv_dense_matrix_t ccv_reshape(ccv_dense_matrix_t* a, int y, int x, int rows, int cols)
1240
1
{
1241
1
  assert(y + rows <= a->rows);
1242
1
  assert(x + cols <= a->cols);
1243
1
  assert(x >= 0 && y >= 0);
1244
1
  ccv_dense_matrix_t b = {
1245
1
    .type = (CCV_UNMANAGED | CCV_GET_DATA_TYPE(a->type) | CCV_GET_CHANNEL(a->type) | CCV_NO_DATA_ALLOC | CCV_MATRIX_DENSE) & ~CCV_GARBAGE,
1246
1
    .rows = rows,
1247
1
    .cols = cols,
1248
1
    .step = a->step,
1249
1
    .refcount = 0,
1250
1
    .sig = 0,
1251
1
    .tb.u8 = 0,
1252
1
    .data.u8 = ccv_get_dense_matrix_cell(a, y, x, 0),
1253
1
  };
1254
1
  return b;
1255
1
}
1256
1257
void ccv_move(ccv_matrix_t* a, ccv_matrix_t** b, int btype, int y, int x)
1258
0
{
1259
0
  int type = *(int*)a;
1260
0
  if (type & CCV_MATRIX_DENSE)
1261
0
  {
1262
0
    ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);
1263
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);
1264
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);
1265
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);
1266
0
    ccv_object_return_if_cached(, db);
1267
0
    int i, j, ch = CCV_GET_CHANNEL(da->type);
1268
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;
1269
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;
1270
0
#define for_block(_for_set, _for_get) \
1271
0
    for (i = abs(y); i < db->rows; i++) \
1272
0
    { \
1273
0
      for (j = abs(x) * ch; j < db->cols * ch; j++) \
1274
0
      { \
1275
0
        _for_set(b_ptr, j, _for_get(a_ptr, j, 0), 0); \
1276
0
      } \
1277
0
      a_ptr += da->step; \
1278
0
      b_ptr += db->step; \
1279
0
    }
1280
0
    ccv_matrix_setter(db->type, ccv_matrix_getter, da->type, for_block);
1281
0
#undef for_block
1282
0
  } else if (type & CCV_MATRIX_SPARSE) {
1283
0
  }
1284
0
}
1285
1286
// the code are shamelessly copied from ftp://ftp.fox-toolkit.org/pub/fasthalffloatconversion.pdf, assuming in Public Domain
1287
1288
static uint16_t _ccv_base_table[512] = {
1289
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
1290
  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
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, 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100,
1296
  0x200, 0x400, 0x800, 0xc00, 0x1000, 0x1400, 0x1800, 0x1c00, 0x2000, 0x2400, 0x2800, 0x2c00, 0x3000, 0x3400, 0x3800, 0x3c00,
1297
  0x4000, 0x4400, 0x4800, 0x4c00, 0x5000, 0x5400, 0x5800, 0x5c00, 0x6000, 0x6400, 0x6800, 0x6c00, 0x7000, 0x7400, 0x7800, 0x7c00,
1298
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00,
1299
  0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 0x7c00, 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
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
1306
  0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000, 0x8000,
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, 0x8001, 0x8002, 0x8004, 0x8008, 0x8010, 0x8020, 0x8040, 0x8080, 0x8100,
1312
  0x8200, 0x8400, 0x8800, 0x8c00, 0x9000, 0x9400, 0x9800, 0x9c00, 0xa000, 0xa400, 0xa800, 0xac00, 0xb000, 0xb400, 0xb800, 0xbc00,
1313
  0xc000, 0xc400, 0xc800, 0xcc00, 0xd000, 0xd400, 0xd800, 0xdc00, 0xe000, 0xe400, 0xe800, 0xec00, 0xf000, 0xf400, 0xf800, 0xfc00,
1314
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00,
1315
  0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 0xfc00, 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
};
1322
1323
static uint8_t _ccv_shift_table[512] = {
1324
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1325
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
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, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0xf,
1331
  0xe, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd,
1332
  0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0x18,
1333
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1334
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 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, 0xd,
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, 0x18,
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, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0xf,
1347
  0xe, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd,
1348
  0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0xd, 0x18,
1349
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18,
1350
  0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 0x18, 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, 0xd,
1356
};
1357
1358
void ccv_float_to_half_precision(float* f, uint16_t* h, size_t len)
1359
2.84M
{
1360
2.84M
  int i;
1361
2.84M
  uint32_t* u = (uint32_t*)f;
1362
5.42G
  for (i = 0; i < len; 
i++5.41G
)
1363
5.41G
    h[i] = _ccv_base_table[(u[i] >> 23) & 0x1ff] + ((u[i] & 0x007fffff) >> _ccv_shift_table[(u[i] >> 23) & 0x1ff]);
1364
2.84M
}
1365
1366
static uint32_t _ccv_mantissa_table[2048] = {
1367
  0x0, 0x33800000, 0x34000000, 0x34400000, 0x34800000, 0x34a00000, 0x34c00000, 0x34e00000,
1368
  0x35000000, 0x35100000, 0x35200000, 0x35300000, 0x35400000, 0x35500000, 0x35600000, 0x35700000,
1369
  0x35800000, 0x35880000, 0x35900000, 0x35980000, 0x35a00000, 0x35a80000, 0x35b00000, 0x35b80000,
1370
  0x35c00000, 0x35c80000, 0x35d00000, 0x35d80000, 0x35e00000, 0x35e80000, 0x35f00000, 0x35f80000,
1371
  0x36000000, 0x36040000, 0x36080000, 0x360c0000, 0x36100000, 0x36140000, 0x36180000, 0x361c0000,
1372
  0x36200000, 0x36240000, 0x36280000, 0x362c0000, 0x36300000, 0x36340000, 0x36380000, 0x363c0000,
1373
  0x36400000, 0x36440000, 0x36480000, 0x364c0000, 0x36500000, 0x36540000, 0x36580000, 0x365c0000,
1374
  0x36600000, 0x36640000, 0x36680000, 0x366c0000, 0x36700000, 0x36740000, 0x36780000, 0x367c0000,
1375
  0x36800000, 0x36820000, 0x36840000, 0x36860000, 0x36880000, 0x368a0000, 0x368c0000, 0x368e0000,
1376
  0x36900000, 0x36920000, 0x36940000, 0x36960000, 0x36980000, 0x369a0000, 0x369c0000, 0x369e0000,
1377
  0x36a00000, 0x36a20000, 0x36a40000, 0x36a60000, 0x36a80000, 0x36aa0000, 0x36ac0000, 0x36ae0000,
1378
  0x36b00000, 0x36b20000, 0x36b40000, 0x36b60000, 0x36b80000, 0x36ba0000, 0x36bc0000, 0x36be0000,
1379
  0x36c00000, 0x36c20000, 0x36c40000, 0x36c60000, 0x36c80000, 0x36ca0000, 0x36cc0000, 0x36ce0000,
1380
  0x36d00000, 0x36d20000, 0x36d40000, 0x36d60000, 0x36d80000, 0x36da0000, 0x36dc0000, 0x36de0000,
1381
  0x36e00000, 0x36e20000, 0x36e40000, 0x36e60000, 0x36e80000, 0x36ea0000, 0x36ec0000, 0x36ee0000,
1382
  0x36f00000, 0x36f20000, 0x36f40000, 0x36f60000, 0x36f80000, 0x36fa0000, 0x36fc0000, 0x36fe0000,
1383
  0x37000000, 0x37010000, 0x37020000, 0x37030000, 0x37040000, 0x37050000, 0x37060000, 0x37070000,
1384
  0x37080000, 0x37090000, 0x370a0000, 0x370b0000, 0x370c0000, 0x370d0000, 0x370e0000, 0x370f0000,
1385
  0x37100000, 0x37110000, 0x37120000, 0x37130000, 0x37140000, 0x37150000, 0x37160000, 0x37170000,
1386
  0x37180000, 0x37190000, 0x371a0000, 0x371b0000, 0x371c0000, 0x371d0000, 0x371e0000, 0x371f0000,
1387
  0x37200000, 0x37210000, 0x37220000, 0x37230000, 0x37240000, 0x37250000, 0x37260000, 0x37270000,
1388
  0x37280000, 0x37290000, 0x372a0000, 0x372b0000, 0x372c0000, 0x372d0000, 0x372e0000, 0x372f0000,
1389
  0x37300000, 0x37310000, 0x37320000, 0x37330000, 0x37340000, 0x37350000, 0x37360000, 0x37370000,
1390
  0x37380000, 0x37390000, 0x373a0000, 0x373b0000, 0x373c0000, 0x373d0000, 0x373e0000, 0x373f0000,
1391
  0x37400000, 0x37410000, 0x37420000, 0x37430000, 0x37440000, 0x37450000, 0x37460000, 0x37470000,
1392
  0x37480000, 0x37490000, 0x374a0000, 0x374b0000, 0x374c0000, 0x374d0000, 0x374e0000, 0x374f0000,
1393
  0x37500000, 0x37510000, 0x37520000, 0x37530000, 0x37540000, 0x37550000, 0x37560000, 0x37570000,
1394
  0x37580000, 0x37590000, 0x375a0000, 0x375b0000, 0x375c0000, 0x375d0000, 0x375e0000, 0x375f0000,
1395
  0x37600000, 0x37610000, 0x37620000, 0x37630000, 0x37640000, 0x37650000, 0x37660000, 0x37670000,
1396
  0x37680000, 0x37690000, 0x376a0000, 0x376b0000, 0x376c0000, 0x376d0000, 0x376e0000, 0x376f0000,
1397
  0x37700000, 0x37710000, 0x37720000, 0x37730000, 0x37740000, 0x37750000, 0x37760000, 0x37770000,
1398
  0x37780000, 0x37790000, 0x377a0000, 0x377b0000, 0x377c0000, 0x377d0000, 0x377e0000, 0x377f0000,
1399
  0x37800000, 0x37808000, 0x37810000, 0x37818000, 0x37820000, 0x37828000, 0x37830000, 0x37838000,
1400
  0x37840000, 0x37848000, 0x37850000, 0x37858000, 0x37860000, 0x37868000, 0x37870000, 0x37878000,
1401
  0x37880000, 0x37888000, 0x37890000, 0x37898000, 0x378a0000, 0x378a8000, 0x378b0000, 0x378b8000,
1402
  0x378c0000, 0x378c8000, 0x378d0000, 0x378d8000, 0x378e0000, 0x378e8000, 0x378f0000, 0x378f8000,
1403
  0x37900000, 0x37908000, 0x37910000, 0x37918000, 0x37920000, 0x37928000, 0x37930000, 0x37938000,
1404
  0x37940000, 0x37948000, 0x37950000, 0x37958000, 0x37960000, 0x37968000, 0x37970000, 0x37978000,
1405
  0x37980000, 0x37988000, 0x37990000, 0x37998000, 0x379a0000, 0x379a8000, 0x379b0000, 0x379b8000,
1406
  0x379c0000, 0x379c8000, 0x379d0000, 0x379d8000, 0x379e0000, 0x379e8000, 0x379f0000, 0x379f8000,
1407
  0x37a00000, 0x37a08000, 0x37a10000, 0x37a18000, 0x37a20000, 0x37a28000, 0x37a30000, 0x37a38000,
1408
  0x37a40000, 0x37a48000, 0x37a50000, 0x37a58000, 0x37a60000, 0x37a68000, 0x37a70000, 0x37a78000,
1409
  0x37a80000, 0x37a88000, 0x37a90000, 0x37a98000, 0x37aa0000, 0x37aa8000, 0x37ab0000, 0x37ab8000,
1410
  0x37ac0000, 0x37ac8000, 0x37ad0000, 0x37ad8000, 0x37ae0000, 0x37ae8000, 0x37af0000, 0x37af8000,
1411
  0x37b00000, 0x37b08000, 0x37b10000, 0x37b18000, 0x37b20000, 0x37b28000, 0x37b30000, 0x37b38000,
1412
  0x37b40000, 0x37b48000, 0x37b50000, 0x37b58000, 0x37b60000, 0x37b68000, 0x37b70000, 0x37b78000,
1413
  0x37b80000, 0x37b88000, 0x37b90000, 0x37b98000, 0x37ba0000, 0x37ba8000, 0x37bb0000, 0x37bb8000,
1414
  0x37bc0000, 0x37bc8000, 0x37bd0000, 0x37bd8000, 0x37be0000, 0x37be8000, 0x37bf0000, 0x37bf8000,
1415
  0x37c00000, 0x37c08000, 0x37c10000, 0x37c18000, 0x37c20000, 0x37c28000, 0x37c30000, 0x37c38000,
1416
  0x37c40000, 0x37c48000, 0x37c50000, 0x37c58000, 0x37c60000, 0x37c68000, 0x37c70000, 0x37c78000,
1417
  0x37c80000, 0x37c88000, 0x37c90000, 0x37c98000, 0x37ca0000, 0x37ca8000, 0x37cb0000, 0x37cb8000,
1418
  0x37cc0000, 0x37cc8000, 0x37cd0000, 0x37cd8000, 0x37ce0000, 0x37ce8000, 0x37cf0000, 0x37cf8000,
1419
  0x37d00000, 0x37d08000, 0x37d10000, 0x37d18000, 0x37d20000, 0x37d28000, 0x37d30000, 0x37d38000,
1420
  0x37d40000, 0x37d48000, 0x37d50000, 0x37d58000, 0x37d60000, 0x37d68000, 0x37d70000, 0x37d78000,
1421
  0x37d80000, 0x37d88000, 0x37d90000, 0x37d98000, 0x37da0000, 0x37da8000, 0x37db0000, 0x37db8000,
1422
  0x37dc0000, 0x37dc8000, 0x37dd0000, 0x37dd8000, 0x37de0000, 0x37de8000, 0x37df0000, 0x37df8000,
1423
  0x37e00000, 0x37e08000, 0x37e10000, 0x37e18000, 0x37e20000, 0x37e28000, 0x37e30000, 0x37e38000,
1424
  0x37e40000, 0x37e48000, 0x37e50000, 0x37e58000, 0x37e60000, 0x37e68000, 0x37e70000, 0x37e78000,
1425
  0x37e80000, 0x37e88000, 0x37e90000, 0x37e98000, 0x37ea0000, 0x37ea8000, 0x37eb0000, 0x37eb8000,
1426
  0x37ec0000, 0x37ec8000, 0x37ed0000, 0x37ed8000, 0x37ee0000, 0x37ee8000, 0x37ef0000, 0x37ef8000,
1427
  0x37f00000, 0x37f08000, 0x37f10000, 0x37f18000, 0x37f20000, 0x37f28000, 0x37f30000, 0x37f38000,
1428
  0x37f40000, 0x37f48000, 0x37f50000, 0x37f58000, 0x37f60000, 0x37f68000, 0x37f70000, 0x37f78000,
1429
  0x37f80000, 0x37f88000, 0x37f90000, 0x37f98000, 0x37fa0000, 0x37fa8000, 0x37fb0000, 0x37fb8000,
1430
  0x37fc0000, 0x37fc8000, 0x37fd0000, 0x37fd8000, 0x37fe0000, 0x37fe8000, 0x37ff0000, 0x37ff8000,
1431
  0x38000000, 0x38004000, 0x38008000, 0x3800c000, 0x38010000, 0x38014000, 0x38018000, 0x3801c000,
1432
  0x38020000, 0x38024000, 0x38028000, 0x3802c000, 0x38030000, 0x38034000, 0x38038000, 0x3803c000,
1433
  0x38040000, 0x38044000, 0x38048000, 0x3804c000, 0x38050000, 0x38054000, 0x38058000, 0x3805c000,
1434
  0x38060000, 0x38064000, 0x38068000, 0x3806c000, 0x38070000, 0x38074000, 0x38078000, 0x3807c000,
1435
  0x38080000, 0x38084000, 0x38088000, 0x3808c000, 0x38090000, 0x38094000, 0x38098000, 0x3809c000,
1436
  0x380a0000, 0x380a4000, 0x380a8000, 0x380ac000, 0x380b0000, 0x380b4000, 0x380b8000, 0x380bc000,
1437
  0x380c0000, 0x380c4000, 0x380c8000, 0x380cc000, 0x380d0000, 0x380d4000, 0x380d8000, 0x380dc000,
1438
  0x380e0000, 0x380e4000, 0x380e8000, 0x380ec000, 0x380f0000, 0x380f4000, 0x380f8000, 0x380fc000,
1439
  0x38100000, 0x38104000, 0x38108000, 0x3810c000, 0x38110000, 0x38114000, 0x38118000, 0x3811c000,
1440
  0x38120000, 0x38124000, 0x38128000, 0x3812c000, 0x38130000, 0x38134000, 0x38138000, 0x3813c000,
1441
  0x38140000, 0x38144000, 0x38148000, 0x3814c000, 0x38150000, 0x38154000, 0x38158000, 0x3815c000,
1442
  0x38160000, 0x38164000, 0x38168000, 0x3816c000, 0x38170000, 0x38174000, 0x38178000, 0x3817c000,
1443
  0x38180000, 0x38184000, 0x38188000, 0x3818c000, 0x38190000, 0x38194000, 0x38198000, 0x3819c000,
1444
  0x381a0000, 0x381a4000, 0x381a8000, 0x381ac000, 0x381b0000, 0x381b4000, 0x381b8000, 0x381bc000,
1445
  0x381c0000, 0x381c4000, 0x381c8000, 0x381cc000, 0x381d0000, 0x381d4000, 0x381d8000, 0x381dc000,
1446
  0x381e0000, 0x381e4000, 0x381e8000, 0x381ec000, 0x381f0000, 0x381f4000, 0x381f8000, 0x381fc000,
1447
  0x38200000, 0x38204000, 0x38208000, 0x3820c000, 0x38210000, 0x38214000, 0x38218000, 0x3821c000,
1448
  0x38220000, 0x38224000, 0x38228000, 0x3822c000, 0x38230000, 0x38234000, 0x38238000, 0x3823c000,
1449
  0x38240000, 0x38244000, 0x38248000, 0x3824c000, 0x38250000, 0x38254000, 0x38258000, 0x3825c000,
1450
  0x38260000, 0x38264000, 0x38268000, 0x3826c000, 0x38270000, 0x38274000, 0x38278000, 0x3827c000,
1451
  0x38280000, 0x38284000, 0x38288000, 0x3828c000, 0x38290000, 0x38294000, 0x38298000, 0x3829c000,
1452
  0x382a0000, 0x382a4000, 0x382a8000, 0x382ac000, 0x382b0000, 0x382b4000, 0x382b8000, 0x382bc000,
1453
  0x382c0000, 0x382c4000, 0x382c8000, 0x382cc000, 0x382d0000, 0x382d4000, 0x382d8000, 0x382dc000,
1454
  0x382e0000, 0x382e4000, 0x382e8000, 0x382ec000, 0x382f0000, 0x382f4000, 0x382f8000, 0x382fc000,
1455
  0x38300000, 0x38304000, 0x38308000, 0x3830c000, 0x38310000, 0x38314000, 0x38318000, 0x3831c000,
1456
  0x38320000, 0x38324000, 0x38328000, 0x3832c000, 0x38330000, 0x38334000, 0x38338000, 0x3833c000,
1457
  0x38340000, 0x38344000, 0x38348000, 0x3834c000, 0x38350000, 0x38354000, 0x38358000, 0x3835c000,
1458
  0x38360000, 0x38364000, 0x38368000, 0x3836c000, 0x38370000, 0x38374000, 0x38378000, 0x3837c000,
1459
  0x38380000, 0x38384000, 0x38388000, 0x3838c000, 0x38390000, 0x38394000, 0x38398000, 0x3839c000,
1460
  0x383a0000, 0x383a4000, 0x383a8000, 0x383ac000, 0x383b0000, 0x383b4000, 0x383b8000, 0x383bc000,
1461
  0x383c0000, 0x383c4000, 0x383c8000, 0x383cc000, 0x383d0000, 0x383d4000, 0x383d8000, 0x383dc000,
1462
  0x383e0000, 0x383e4000, 0x383e8000, 0x383ec000, 0x383f0000, 0x383f4000, 0x383f8000, 0x383fc000,
1463
  0x38400000, 0x38404000, 0x38408000, 0x3840c000, 0x38410000, 0x38414000, 0x38418000, 0x3841c000,
1464
  0x38420000, 0x38424000, 0x38428000, 0x3842c000, 0x38430000, 0x38434000, 0x38438000, 0x3843c000,
1465
  0x38440000, 0x38444000, 0x38448000, 0x3844c000, 0x38450000, 0x38454000, 0x38458000, 0x3845c000,
1466
  0x38460000, 0x38464000, 0x38468000, 0x3846c000, 0x38470000, 0x38474000, 0x38478000, 0x3847c000,
1467
  0x38480000, 0x38484000, 0x38488000, 0x3848c000, 0x38490000, 0x38494000, 0x38498000, 0x3849c000,
1468
  0x384a0000, 0x384a4000, 0x384a8000, 0x384ac000, 0x384b0000, 0x384b4000, 0x384b8000, 0x384bc000,
1469
  0x384c0000, 0x384c4000, 0x384c8000, 0x384cc000, 0x384d0000, 0x384d4000, 0x384d8000, 0x384dc000,
1470
  0x384e0000, 0x384e4000, 0x384e8000, 0x384ec000, 0x384f0000, 0x384f4000, 0x384f8000, 0x384fc000,
1471
  0x38500000, 0x38504000, 0x38508000, 0x3850c000, 0x38510000, 0x38514000, 0x38518000, 0x3851c000,
1472
  0x38520000, 0x38524000, 0x38528000, 0x3852c000, 0x38530000, 0x38534000, 0x38538000, 0x3853c000,
1473
  0x38540000, 0x38544000, 0x38548000, 0x3854c000, 0x38550000, 0x38554000, 0x38558000, 0x3855c000,
1474
  0x38560000, 0x38564000, 0x38568000, 0x3856c000, 0x38570000, 0x38574000, 0x38578000, 0x3857c000,
1475
  0x38580000, 0x38584000, 0x38588000, 0x3858c000, 0x38590000, 0x38594000, 0x38598000, 0x3859c000,
1476
  0x385a0000, 0x385a4000, 0x385a8000, 0x385ac000, 0x385b0000, 0x385b4000, 0x385b8000, 0x385bc000,
1477
  0x385c0000, 0x385c4000, 0x385c8000, 0x385cc000, 0x385d0000, 0x385d4000, 0x385d8000, 0x385dc000,
1478
  0x385e0000, 0x385e4000, 0x385e8000, 0x385ec000, 0x385f0000, 0x385f4000, 0x385f8000, 0x385fc000,
1479
  0x38600000, 0x38604000, 0x38608000, 0x3860c000, 0x38610000, 0x38614000, 0x38618000, 0x3861c000,
1480
  0x38620000, 0x38624000, 0x38628000, 0x3862c000, 0x38630000, 0x38634000, 0x38638000, 0x3863c000,
1481
  0x38640000, 0x38644000, 0x38648000, 0x3864c000, 0x38650000, 0x38654000, 0x38658000, 0x3865c000,
1482
  0x38660000, 0x38664000, 0x38668000, 0x3866c000, 0x38670000, 0x38674000, 0x38678000, 0x3867c000,
1483
  0x38680000, 0x38684000, 0x38688000, 0x3868c000, 0x38690000, 0x38694000, 0x38698000, 0x3869c000,
1484
  0x386a0000, 0x386a4000, 0x386a8000, 0x386ac000, 0x386b0000, 0x386b4000, 0x386b8000, 0x386bc000,
1485
  0x386c0000, 0x386c4000, 0x386c8000, 0x386cc000, 0x386d0000, 0x386d4000, 0x386d8000, 0x386dc000,
1486
  0x386e0000, 0x386e4000, 0x386e8000, 0x386ec000, 0x386f0000, 0x386f4000, 0x386f8000, 0x386fc000,
1487
  0x38700000, 0x38704000, 0x38708000, 0x3870c000, 0x38710000, 0x38714000, 0x38718000, 0x3871c000,
1488
  0x38720000, 0x38724000, 0x38728000, 0x3872c000, 0x38730000, 0x38734000, 0x38738000, 0x3873c000,
1489
  0x38740000, 0x38744000, 0x38748000, 0x3874c000, 0x38750000, 0x38754000, 0x38758000, 0x3875c000,
1490
  0x38760000, 0x38764000, 0x38768000, 0x3876c000, 0x38770000, 0x38774000, 0x38778000, 0x3877c000,
1491
  0x38780000, 0x38784000, 0x38788000, 0x3878c000, 0x38790000, 0x38794000, 0x38798000, 0x3879c000,
1492
  0x387a0000, 0x387a4000, 0x387a8000, 0x387ac000, 0x387b0000, 0x387b4000, 0x387b8000, 0x387bc000,
1493
  0x387c0000, 0x387c4000, 0x387c8000, 0x387cc000, 0x387d0000, 0x387d4000, 0x387d8000, 0x387dc000,
1494
  0x387e0000, 0x387e4000, 0x387e8000, 0x387ec000, 0x387f0000, 0x387f4000, 0x387f8000, 0x387fc000,
1495
  0x38000000, 0x38002000, 0x38004000, 0x38006000, 0x38008000, 0x3800a000, 0x3800c000, 0x3800e000,
1496
  0x38010000, 0x38012000, 0x38014000, 0x38016000, 0x38018000, 0x3801a000, 0x3801c000, 0x3801e000,
1497
  0x38020000, 0x38022000, 0x38024000, 0x38026000, 0x38028000, 0x3802a000, 0x3802c000, 0x3802e000,
1498
  0x38030000, 0x38032000, 0x38034000, 0x38036000, 0x38038000, 0x3803a000, 0x3803c000, 0x3803e000,
1499
  0x38040000, 0x38042000, 0x38044000, 0x38046000, 0x38048000, 0x3804a000, 0x3804c000, 0x3804e000,
1500
  0x38050000, 0x38052000, 0x38054000, 0x38056000, 0x38058000, 0x3805a000, 0x3805c000, 0x3805e000,
1501
  0x38060000, 0x38062000, 0x38064000, 0x38066000, 0x38068000, 0x3806a000, 0x3806c000, 0x3806e000,
1502
  0x38070000, 0x38072000, 0x38074000, 0x38076000, 0x38078000, 0x3807a000, 0x3807c000, 0x3807e000,
1503
  0x38080000, 0x38082000, 0x38084000, 0x38086000, 0x38088000, 0x3808a000, 0x3808c000, 0x3808e000,
1504
  0x38090000, 0x38092000, 0x38094000, 0x38096000, 0x38098000, 0x3809a000, 0x3809c000, 0x3809e000,
1505
  0x380a0000, 0x380a2000, 0x380a4000, 0x380a6000, 0x380a8000, 0x380aa000, 0x380ac000, 0x380ae000,
1506
  0x380b0000, 0x380b2000, 0x380b4000, 0x380b6000, 0x380b8000, 0x380ba000, 0x380bc000, 0x380be000,
1507
  0x380c0000, 0x380c2000, 0x380c4000, 0x380c6000, 0x380c8000, 0x380ca000, 0x380cc000, 0x380ce000,
1508
  0x380d0000, 0x380d2000, 0x380d4000, 0x380d6000, 0x380d8000, 0x380da000, 0x380dc000, 0x380de000,
1509
  0x380e0000, 0x380e2000, 0x380e4000, 0x380e6000, 0x380e8000, 0x380ea000, 0x380ec000, 0x380ee000,
1510
  0x380f0000, 0x380f2000, 0x380f4000, 0x380f6000, 0x380f8000, 0x380fa000, 0x380fc000, 0x380fe000,
1511
  0x38100000, 0x38102000, 0x38104000, 0x38106000, 0x38108000, 0x3810a000, 0x3810c000, 0x3810e000,
1512
  0x38110000, 0x38112000, 0x38114000, 0x38116000, 0x38118000, 0x3811a000, 0x3811c000, 0x3811e000,
1513
  0x38120000, 0x38122000, 0x38124000, 0x38126000, 0x38128000, 0x3812a000, 0x3812c000, 0x3812e000,
1514
  0x38130000, 0x38132000, 0x38134000, 0x38136000, 0x38138000, 0x3813a000, 0x3813c000, 0x3813e000,
1515
  0x38140000, 0x38142000, 0x38144000, 0x38146000, 0x38148000, 0x3814a000, 0x3814c000, 0x3814e000,
1516
  0x38150000, 0x38152000, 0x38154000, 0x38156000, 0x38158000, 0x3815a000, 0x3815c000, 0x3815e000,
1517
  0x38160000, 0x38162000, 0x38164000, 0x38166000, 0x38168000, 0x3816a000, 0x3816c000, 0x3816e000,
1518
  0x38170000, 0x38172000, 0x38174000, 0x38176000, 0x38178000, 0x3817a000, 0x3817c000, 0x3817e000,
1519
  0x38180000, 0x38182000, 0x38184000, 0x38186000, 0x38188000, 0x3818a000, 0x3818c000, 0x3818e000,
1520
  0x38190000, 0x38192000, 0x38194000, 0x38196000, 0x38198000, 0x3819a000, 0x3819c000, 0x3819e000,
1521
  0x381a0000, 0x381a2000, 0x381a4000, 0x381a6000, 0x381a8000, 0x381aa000, 0x381ac000, 0x381ae000,
1522
  0x381b0000, 0x381b2000, 0x381b4000, 0x381b6000, 0x381b8000, 0x381ba000, 0x381bc000, 0x381be000,
1523
  0x381c0000, 0x381c2000, 0x381c4000, 0x381c6000, 0x381c8000, 0x381ca000, 0x381cc000, 0x381ce000,
1524
  0x381d0000, 0x381d2000, 0x381d4000, 0x381d6000, 0x381d8000, 0x381da000, 0x381dc000, 0x381de000,
1525
  0x381e0000, 0x381e2000, 0x381e4000, 0x381e6000, 0x381e8000, 0x381ea000, 0x381ec000, 0x381ee000,
1526
  0x381f0000, 0x381f2000, 0x381f4000, 0x381f6000, 0x381f8000, 0x381fa000, 0x381fc000, 0x381fe000,
1527
  0x38200000, 0x38202000, 0x38204000, 0x38206000, 0x38208000, 0x3820a000, 0x3820c000, 0x3820e000,
1528
  0x38210000, 0x38212000, 0x38214000, 0x38216000, 0x38218000, 0x3821a000, 0x3821c000, 0x3821e000,
1529
  0x38220000, 0x38222000, 0x38224000, 0x38226000, 0x38228000, 0x3822a000, 0x3822c000, 0x3822e000,
1530
  0x38230000, 0x38232000, 0x38234000, 0x38236000, 0x38238000, 0x3823a000, 0x3823c000, 0x3823e000,
1531
  0x38240000, 0x38242000, 0x38244000, 0x38246000, 0x38248000, 0x3824a000, 0x3824c000, 0x3824e000,
1532
  0x38250000, 0x38252000, 0x38254000, 0x38256000, 0x38258000, 0x3825a000, 0x3825c000, 0x3825e000,
1533
  0x38260000, 0x38262000, 0x38264000, 0x38266000, 0x38268000, 0x3826a000, 0x3826c000, 0x3826e000,
1534
  0x38270000, 0x38272000, 0x38274000, 0x38276000, 0x38278000, 0x3827a000, 0x3827c000, 0x3827e000,
1535
  0x38280000, 0x38282000, 0x38284000, 0x38286000, 0x38288000, 0x3828a000, 0x3828c000, 0x3828e000,
1536
  0x38290000, 0x38292000, 0x38294000, 0x38296000, 0x38298000, 0x3829a000, 0x3829c000, 0x3829e000,
1537
  0x382a0000, 0x382a2000, 0x382a4000, 0x382a6000, 0x382a8000, 0x382aa000, 0x382ac000, 0x382ae000,
1538
  0x382b0000, 0x382b2000, 0x382b4000, 0x382b6000, 0x382b8000, 0x382ba000, 0x382bc000, 0x382be000,
1539
  0x382c0000, 0x382c2000, 0x382c4000, 0x382c6000, 0x382c8000, 0x382ca000, 0x382cc000, 0x382ce000,
1540
  0x382d0000, 0x382d2000, 0x382d4000, 0x382d6000, 0x382d8000, 0x382da000, 0x382dc000, 0x382de000,
1541
  0x382e0000, 0x382e2000, 0x382e4000, 0x382e6000, 0x382e8000, 0x382ea000, 0x382ec000, 0x382ee000,
1542
  0x382f0000, 0x382f2000, 0x382f4000, 0x382f6000, 0x382f8000, 0x382fa000, 0x382fc000, 0x382fe000,
1543
  0x38300000, 0x38302000, 0x38304000, 0x38306000, 0x38308000, 0x3830a000, 0x3830c000, 0x3830e000,
1544
  0x38310000, 0x38312000, 0x38314000, 0x38316000, 0x38318000, 0x3831a000, 0x3831c000, 0x3831e000,
1545
  0x38320000, 0x38322000, 0x38324000, 0x38326000, 0x38328000, 0x3832a000, 0x3832c000, 0x3832e000,
1546
  0x38330000, 0x38332000, 0x38334000, 0x38336000, 0x38338000, 0x3833a000, 0x3833c000, 0x3833e000,
1547
  0x38340000, 0x38342000, 0x38344000, 0x38346000, 0x38348000, 0x3834a000, 0x3834c000, 0x3834e000,
1548
  0x38350000, 0x38352000, 0x38354000, 0x38356000, 0x38358000, 0x3835a000, 0x3835c000, 0x3835e000,
1549
  0x38360000, 0x38362000, 0x38364000, 0x38366000, 0x38368000, 0x3836a000, 0x3836c000, 0x3836e000,
1550
  0x38370000, 0x38372000, 0x38374000, 0x38376000, 0x38378000, 0x3837a000, 0x3837c000, 0x3837e000,
1551
  0x38380000, 0x38382000, 0x38384000, 0x38386000, 0x38388000, 0x3838a000, 0x3838c000, 0x3838e000,
1552
  0x38390000, 0x38392000, 0x38394000, 0x38396000, 0x38398000, 0x3839a000, 0x3839c000, 0x3839e000,
1553
  0x383a0000, 0x383a2000, 0x383a4000, 0x383a6000, 0x383a8000, 0x383aa000, 0x383ac000, 0x383ae000,
1554
  0x383b0000, 0x383b2000, 0x383b4000, 0x383b6000, 0x383b8000, 0x383ba000, 0x383bc000, 0x383be000,
1555
  0x383c0000, 0x383c2000, 0x383c4000, 0x383c6000, 0x383c8000, 0x383ca000, 0x383cc000, 0x383ce000,
1556
  0x383d0000, 0x383d2000, 0x383d4000, 0x383d6000, 0x383d8000, 0x383da000, 0x383dc000, 0x383de000,
1557
  0x383e0000, 0x383e2000, 0x383e4000, 0x383e6000, 0x383e8000, 0x383ea000, 0x383ec000, 0x383ee000,
1558
  0x383f0000, 0x383f2000, 0x383f4000, 0x383f6000, 0x383f8000, 0x383fa000, 0x383fc000, 0x383fe000,
1559
  0x38400000, 0x38402000, 0x38404000, 0x38406000, 0x38408000, 0x3840a000, 0x3840c000, 0x3840e000,
1560
  0x38410000, 0x38412000, 0x38414000, 0x38416000, 0x38418000, 0x3841a000, 0x3841c000, 0x3841e000,
1561
  0x38420000, 0x38422000, 0x38424000, 0x38426000, 0x38428000, 0x3842a000, 0x3842c000, 0x3842e000,
1562
  0x38430000, 0x38432000, 0x38434000, 0x38436000, 0x38438000, 0x3843a000, 0x3843c000, 0x3843e000,
1563
  0x38440000, 0x38442000, 0x38444000, 0x38446000, 0x38448000, 0x3844a000, 0x3844c000, 0x3844e000,
1564
  0x38450000, 0x38452000, 0x38454000, 0x38456000, 0x38458000, 0x3845a000, 0x3845c000, 0x3845e000,
1565
  0x38460000, 0x38462000, 0x38464000, 0x38466000, 0x38468000, 0x3846a000, 0x3846c000, 0x3846e000,
1566
  0x38470000, 0x38472000, 0x38474000, 0x38476000, 0x38478000, 0x3847a000, 0x3847c000, 0x3847e000,
1567
  0x38480000, 0x38482000, 0x38484000, 0x38486000, 0x38488000, 0x3848a000, 0x3848c000, 0x3848e000,
1568
  0x38490000, 0x38492000, 0x38494000, 0x38496000, 0x38498000, 0x3849a000, 0x3849c000, 0x3849e000,
1569
  0x384a0000, 0x384a2000, 0x384a4000, 0x384a6000, 0x384a8000, 0x384aa000, 0x384ac000, 0x384ae000,
1570
  0x384b0000, 0x384b2000, 0x384b4000, 0x384b6000, 0x384b8000, 0x384ba000, 0x384bc000, 0x384be000,
1571
  0x384c0000, 0x384c2000, 0x384c4000, 0x384c6000, 0x384c8000, 0x384ca000, 0x384cc000, 0x384ce000,
1572
  0x384d0000, 0x384d2000, 0x384d4000, 0x384d6000, 0x384d8000, 0x384da000, 0x384dc000, 0x384de000,
1573
  0x384e0000, 0x384e2000, 0x384e4000, 0x384e6000, 0x384e8000, 0x384ea000, 0x384ec000, 0x384ee000,
1574
  0x384f0000, 0x384f2000, 0x384f4000, 0x384f6000, 0x384f8000, 0x384fa000, 0x384fc000, 0x384fe000,
1575
  0x38500000, 0x38502000, 0x38504000, 0x38506000, 0x38508000, 0x3850a000, 0x3850c000, 0x3850e000,
1576
  0x38510000, 0x38512000, 0x38514000, 0x38516000, 0x38518000, 0x3851a000, 0x3851c000, 0x3851e000,
1577
  0x38520000, 0x38522000, 0x38524000, 0x38526000, 0x38528000, 0x3852a000, 0x3852c000, 0x3852e000,
1578
  0x38530000, 0x38532000, 0x38534000, 0x38536000, 0x38538000, 0x3853a000, 0x3853c000, 0x3853e000,
1579
  0x38540000, 0x38542000, 0x38544000, 0x38546000, 0x38548000, 0x3854a000, 0x3854c000, 0x3854e000,
1580
  0x38550000, 0x38552000, 0x38554000, 0x38556000, 0x38558000, 0x3855a000, 0x3855c000, 0x3855e000,
1581
  0x38560000, 0x38562000, 0x38564000, 0x38566000, 0x38568000, 0x3856a000, 0x3856c000, 0x3856e000,
1582
  0x38570000, 0x38572000, 0x38574000, 0x38576000, 0x38578000, 0x3857a000, 0x3857c000, 0x3857e000,
1583
  0x38580000, 0x38582000, 0x38584000, 0x38586000, 0x38588000, 0x3858a000, 0x3858c000, 0x3858e000,
1584
  0x38590000, 0x38592000, 0x38594000, 0x38596000, 0x38598000, 0x3859a000, 0x3859c000, 0x3859e000,
1585
  0x385a0000, 0x385a2000, 0x385a4000, 0x385a6000, 0x385a8000, 0x385aa000, 0x385ac000, 0x385ae000,
1586
  0x385b0000, 0x385b2000, 0x385b4000, 0x385b6000, 0x385b8000, 0x385ba000, 0x385bc000, 0x385be000,
1587
  0x385c0000, 0x385c2000, 0x385c4000, 0x385c6000, 0x385c8000, 0x385ca000, 0x385cc000, 0x385ce000,
1588
  0x385d0000, 0x385d2000, 0x385d4000, 0x385d6000, 0x385d8000, 0x385da000, 0x385dc000, 0x385de000,
1589
  0x385e0000, 0x385e2000, 0x385e4000, 0x385e6000, 0x385e8000, 0x385ea000, 0x385ec000, 0x385ee000,
1590
  0x385f0000, 0x385f2000, 0x385f4000, 0x385f6000, 0x385f8000, 0x385fa000, 0x385fc000, 0x385fe000,
1591
  0x38600000, 0x38602000, 0x38604000, 0x38606000, 0x38608000, 0x3860a000, 0x3860c000, 0x3860e000,
1592
  0x38610000, 0x38612000, 0x38614000, 0x38616000, 0x38618000, 0x3861a000, 0x3861c000, 0x3861e000,
1593
  0x38620000, 0x38622000, 0x38624000, 0x38626000, 0x38628000, 0x3862a000, 0x3862c000, 0x3862e000,
1594
  0x38630000, 0x38632000, 0x38634000, 0x38636000, 0x38638000, 0x3863a000, 0x3863c000, 0x3863e000,
1595
  0x38640000, 0x38642000, 0x38644000, 0x38646000, 0x38648000, 0x3864a000, 0x3864c000, 0x3864e000,
1596
  0x38650000, 0x38652000, 0x38654000, 0x38656000, 0x38658000, 0x3865a000, 0x3865c000, 0x3865e000,
1597
  0x38660000, 0x38662000, 0x38664000, 0x38666000, 0x38668000, 0x3866a000, 0x3866c000, 0x3866e000,
1598
  0x38670000, 0x38672000, 0x38674000, 0x38676000, 0x38678000, 0x3867a000, 0x3867c000, 0x3867e000,
1599
  0x38680000, 0x38682000, 0x38684000, 0x38686000, 0x38688000, 0x3868a000, 0x3868c000, 0x3868e000,
1600
  0x38690000, 0x38692000, 0x38694000, 0x38696000, 0x38698000, 0x3869a000, 0x3869c000, 0x3869e000,
1601
  0x386a0000, 0x386a2000, 0x386a4000, 0x386a6000, 0x386a8000, 0x386aa000, 0x386ac000, 0x386ae000,
1602
  0x386b0000, 0x386b2000, 0x386b4000, 0x386b6000, 0x386b8000, 0x386ba000, 0x386bc000, 0x386be000,
1603
  0x386c0000, 0x386c2000, 0x386c4000, 0x386c6000, 0x386c8000, 0x386ca000, 0x386cc000, 0x386ce000,
1604
  0x386d0000, 0x386d2000, 0x386d4000, 0x386d6000, 0x386d8000, 0x386da000, 0x386dc000, 0x386de000,
1605
  0x386e0000, 0x386e2000, 0x386e4000, 0x386e6000, 0x386e8000, 0x386ea000, 0x386ec000, 0x386ee000,
1606
  0x386f0000, 0x386f2000, 0x386f4000, 0x386f6000, 0x386f8000, 0x386fa000, 0x386fc000, 0x386fe000,
1607
  0x38700000, 0x38702000, 0x38704000, 0x38706000, 0x38708000, 0x3870a000, 0x3870c000, 0x3870e000,
1608
  0x38710000, 0x38712000, 0x38714000, 0x38716000, 0x38718000, 0x3871a000, 0x3871c000, 0x3871e000,
1609
  0x38720000, 0x38722000, 0x38724000, 0x38726000, 0x38728000, 0x3872a000, 0x3872c000, 0x3872e000,
1610
  0x38730000, 0x38732000, 0x38734000, 0x38736000, 0x38738000, 0x3873a000, 0x3873c000, 0x3873e000,
1611
  0x38740000, 0x38742000, 0x38744000, 0x38746000, 0x38748000, 0x3874a000, 0x3874c000, 0x3874e000,
1612
  0x38750000, 0x38752000, 0x38754000, 0x38756000, 0x38758000, 0x3875a000, 0x3875c000, 0x3875e000,
1613
  0x38760000, 0x38762000, 0x38764000, 0x38766000, 0x38768000, 0x3876a000, 0x3876c000, 0x3876e000,
1614
  0x38770000, 0x38772000, 0x38774000, 0x38776000, 0x38778000, 0x3877a000, 0x3877c000, 0x3877e000,
1615
  0x38780000, 0x38782000, 0x38784000, 0x38786000, 0x38788000, 0x3878a000, 0x3878c000, 0x3878e000,
1616
  0x38790000, 0x38792000, 0x38794000, 0x38796000, 0x38798000, 0x3879a000, 0x3879c000, 0x3879e000,
1617
  0x387a0000, 0x387a2000, 0x387a4000, 0x387a6000, 0x387a8000, 0x387aa000, 0x387ac000, 0x387ae000,
1618
  0x387b0000, 0x387b2000, 0x387b4000, 0x387b6000, 0x387b8000, 0x387ba000, 0x387bc000, 0x387be000,
1619
  0x387c0000, 0x387c2000, 0x387c4000, 0x387c6000, 0x387c8000, 0x387ca000, 0x387cc000, 0x387ce000,
1620
  0x387d0000, 0x387d2000, 0x387d4000, 0x387d6000, 0x387d8000, 0x387da000, 0x387dc000, 0x387de000,
1621
  0x387e0000, 0x387e2000, 0x387e4000, 0x387e6000, 0x387e8000, 0x387ea000, 0x387ec000, 0x387ee000,
1622
  0x387f0000, 0x387f2000, 0x387f4000, 0x387f6000, 0x387f8000, 0x387fa000, 0x387fc000, 0x387fe000,
1623
};
1624
1625
static uint32_t _ccv_exponent_table[64] = {
1626
  0x0, 0x800000, 0x1000000, 0x1800000, 0x2000000, 0x2800000, 0x3000000, 0x3800000,
1627
  0x4000000, 0x4800000, 0x5000000, 0x5800000, 0x6000000, 0x6800000, 0x7000000, 0x7800000,
1628
  0x8000000, 0x8800000, 0x9000000, 0x9800000, 0xa000000, 0xa800000, 0xb000000, 0xb800000,
1629
  0xc000000, 0xc800000, 0xd000000, 0xd800000, 0xe000000, 0xe800000, 0xf000000, 0x47800000,
1630
  0x80000000, 0x80800000, 0x81000000, 0x81800000, 0x82000000, 0x82800000, 0x83000000, 0x83800000,
1631
  0x84000000, 0x84800000, 0x85000000, 0x85800000, 0x86000000, 0x86800000, 0x87000000, 0x87800000,
1632
  0x88000000, 0x88800000, 0x89000000, 0x89800000, 0x8a000000, 0x8a800000, 0x8b000000, 0x8b800000,
1633
  0x8c000000, 0x8c800000, 0x8d000000, 0x8d800000, 0x8e000000, 0x8e800000, 0x8f000000, 0xc7800000,
1634
};
1635
1636
static uint16_t _ccv_offset_table[64] = {
1637
  0x0, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1638
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1639
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1640
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1641
  0x0, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1642
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1643
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1644
  0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400, 0x400,
1645
};
1646
1647
void ccv_half_precision_to_float(uint16_t* h, float* f, size_t len)
1648
149
{
1649
149
  int i;
1650
149
  uint32_t* u = (uint32_t*)f;
1651
299M
  for (i = 0; i < len; 
i++299M
)
1652
299M
    u[i] = _ccv_mantissa_table[_ccv_offset_table[h[i] >> 10] + (h[i] & 0x3ff)] + _ccv_exponent_table[h[i] >> 10];
1653
149
}
1654
1655
void ccv_array_push(ccv_array_t* array, const void* r)
1656
27.4M
{
1657
27.4M
  array->rnum++;
1658
27.4M
  if (array->rnum > array->size)
1659
74.7k
  {
1660
74.7k
    array->size = ccv_max(array->size * 3 / 2, array->size + 1);
1661
74.7k
    array->data = ccrealloc(array->data, (size_t)array->size * (size_t)array->rsize);
1662
74.7k
  }
1663
27.4M
  memcpy(ccv_array_get(array, array->rnum - 1), r, array->rsize);
1664
27.4M
}
1665
1666
void ccv_array_zero(ccv_array_t* array)
1667
69
{
1668
69
  memset(array->data, 0, (size_t)array->size * (size_t)array->rsize);
1669
69
}
1670
1671
void ccv_array_resize(ccv_array_t* array, int rnum)
1672
19.5k
{
1673
19.5k
  if (rnum > array->size)
1674
8.98k
  {
1675
8.98k
    array->size = ccv_max(array->size * 3 / 2, rnum);
1676
8.98k
    array->data = ccrealloc(array->data, (size_t)array->size * (size_t)array->rsize);
1677
8.98k
  }
1678
19.5k
  memset(ccv_array_get(array, array->rnum), 0, (size_t)array->rsize * (size_t)(rnum - array->rnum));
1679
19.5k
  array->rnum = rnum;
1680
19.5k
}
1681
1682
void ccv_array_clear(ccv_array_t* array)
1683
32.1k
{
1684
32.1k
  array->rnum = 0;
1685
32.1k
}
1686
1687
typedef struct ccv_ptree_node_t
1688
{
1689
  struct ccv_ptree_node_t* parent;
1690
  void* element;
1691
  int rank;
1692
} ccv_ptree_node_t;
1693
1694
/* the code for grouping array is adopted from OpenCV's cvSeqPartition func, it is essentially a find-union algorithm */
1695
int ccv_array_group(ccv_array_t* array, ccv_array_t** index, ccv_array_group_f gfunc, void* data)
1696
1
{
1697
1
  int i, j;
1698
1
  ccv_ptree_node_t* node = (ccv_ptree_node_t*)ccmalloc(array->rnum * sizeof(ccv_ptree_node_t));
1699
9
  for (i = 0; i < array->rnum; 
i++8
)
1700
8
  {
1701
8
    node[i].parent = 0;
1702
8
    node[i].element = ccv_array_get(array, i);
1703
8
    node[i].rank = 0;
1704
8
  }
1705
9
  for (i = 0; i < array->rnum; 
i++8
)
1706
8
  {
1707
8
    if (!node[i].element)
1708
0
      continue;
1709
8
    ccv_ptree_node_t* root = node + i;
1710
9
    while (root->parent)
1711
1
      root = root->parent;
1712
72
    for (j = 0; j < array->rnum; 
j++64
)
1713
64
    {
1714
64
      if( i != j && 
node[j].element56
&&
gfunc(node[i].element, node[j].element, data)56
)
1715
8
      {
1716
8
        ccv_ptree_node_t* root2 = node + j;
1717
8
1718
12
        while(root2->parent)
1719
4
          root2 = root2->parent;
1720
8
1721
8
        if(root2 != root)
1722
3
        {
1723
3
          if(root->rank > root2->rank)
1724
1
            root2->parent = root;
1725
2
          else
1726
2
          {
1727
2
            root->parent = root2;
1728
2
            root2->rank += root->rank == root2->rank;
1729
2
            root = root2;
1730
2
          }
1731
3
1732
3
          /* compress path from node2 to the root: */
1733
3
          ccv_ptree_node_t* node2 = node + j;
1734
4
          while(node2->parent)
1735
1
          {
1736
1
            ccv_ptree_node_t* temp = node2;
1737
1
            node2 = node2->parent;
1738
1
            temp->parent = root;
1739
1
          }
1740
3
1741
3
          /* compress path from node to the root: */
1742
3
          node2 = node + i;
1743
6
          while(node2->parent)
1744
3
          {
1745
3
            ccv_ptree_node_t* temp = node2;
1746
3
            node2 = node2->parent;
1747
3
            temp->parent = root;
1748
3
          }
1749
3
        }
1750
8
      }
1751
64
    }
1752
8
  }
1753
1
  if (*index == 0)
1754
1
    *index = ccv_array_new(sizeof(int), array->rnum, 0);
1755
0
  else
1756
0
    ccv_array_clear(*index);
1757
1
  ccv_array_t* idx = *index;
1758
1
1759
1
  int class_idx = 0;
1760
9
  for(i = 0; i < array->rnum; 
i++8
)
1761
8
  {
1762
8
    j = -1;
1763
8
    ccv_ptree_node_t* node1 = node + i;
1764
8
    if(node1->element)
1765
8
    {
1766
11
      while(node1->parent)
1767
3
        node1 = node1->parent;
1768
8
      if(node1->rank >= 0)
1769
5
        node1->rank = ~class_idx++;
1770
8
      j = ~node1->rank;
1771
8
    }
1772
8
    ccv_array_push(idx, &j);
1773
8
  }
1774
1
  ccfree(node);
1775
1
  return class_idx;
1776
1
}
1777
1778
ccv_contour_t* ccv_contour_new(int set)
1779
0
{
1780
0
  ccv_contour_t* contour = (ccv_contour_t*)ccmalloc(sizeof(ccv_contour_t));
1781
0
  contour->rect.x = contour->rect.y =
1782
0
  contour->rect.width = contour->rect.height = 0;
1783
0
  contour->size = 0;
1784
0
  if (set)
1785
0
    contour->set = ccv_array_new(sizeof(ccv_point_t), 5, 0);
1786
0
  else
1787
0
    contour->set = 0;
1788
0
  return contour;
1789
0
}
1790
1791
void ccv_contour_push(ccv_contour_t* contour, ccv_point_t point)
1792
0
{
1793
0
  if (contour->size == 0)
1794
0
  {
1795
0
    contour->rect.x = point.x;
1796
0
    contour->rect.y = point.y;
1797
0
    contour->rect.width = contour->rect.height = 1;
1798
0
    contour->m10 = point.x;
1799
0
    contour->m01 = point.y;
1800
0
    contour->m11 = point.x * point.y;
1801
0
    contour->m20 = point.x * point.x;
1802
0
    contour->m02 = point.y * point.y;
1803
0
    contour->size = 1;
1804
0
  } else {
1805
0
    if (point.x < contour->rect.x)
1806
0
    {
1807
0
      contour->rect.width += contour->rect.x - point.x;
1808
0
      contour->rect.x = point.x;
1809
0
    } else if (point.x > contour->rect.x + contour->rect.width - 1) {
1810
0
      contour->rect.width = point.x - contour->rect.x + 1;
1811
0
    }
1812
0
    if (point.y < contour->rect.y)
1813
0
    {
1814
0
      contour->rect.height += contour->rect.y - point.y;
1815
0
      contour->rect.y = point.y;
1816
0
    } else if (point.y > contour->rect.y + contour->rect.height - 1) {
1817
0
      contour->rect.height = point.y - contour->rect.y + 1;
1818
0
    }
1819
0
    contour->m10 += point.x;
1820
0
    contour->m01 += point.y;
1821
0
    contour->m11 += point.x * point.y;
1822
0
    contour->m20 += point.x * point.x;
1823
0
    contour->m02 += point.y * point.y;
1824
0
    contour->size++;
1825
0
  }
1826
0
  if (contour->set)
1827
0
    ccv_array_push(contour->set, &point);
1828
0
}
1829
1830
void ccv_contour_free(ccv_contour_t* contour)
1831
0
{
1832
0
  if (contour->set)
1833
0
    ccv_array_free(contour->set);
1834
0
  ccfree(contour);
1835
0
}