blob: 71c5f0ca48b7047a6722c960397344161a39b120 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
/* Copyright (c) 2020 tevador <tevador@gmail.com> */
/* See LICENSE for licensing information */
#ifndef SOLVER_HEAP_H
#define SOLVER_HEAP_H
#include <stdint.h>
#include <equix.h>
#define INDEX_SPACE (UINT32_C(1) << 16)
#define NUM_COARSE_BUCKETS 256
#define NUM_FINE_BUCKETS 128
#define COARSE_BUCKET_ITEMS 336
#define FINE_BUCKET_ITEMS 12
typedef uint16_t fine_item;
typedef struct fine_bucket {
fine_item items[FINE_BUCKET_ITEMS];
} fine_bucket;
typedef struct fine_hashtab {
uint8_t counts[NUM_FINE_BUCKETS];
fine_bucket buckets[NUM_FINE_BUCKETS];
} fine_hashtab;
typedef equix_idx stage1_idx_item; /* 16 bits */
typedef uint64_t stage1_data_item; /* 52 bits */
typedef struct stage1_idx_bucket {
stage1_idx_item items[COARSE_BUCKET_ITEMS];
} stage1_idx_bucket;
typedef struct stage1_data_bucket {
stage1_data_item items[COARSE_BUCKET_ITEMS];
} stage1_data_bucket;
typedef struct stage1_idx_hashtab {
uint16_t counts[NUM_COARSE_BUCKETS];
stage1_idx_bucket buckets[NUM_COARSE_BUCKETS];
} stage1_idx_hashtab;
typedef struct stage1_data_hashtab {
stage1_data_bucket buckets[NUM_COARSE_BUCKETS];
} stage1_data_hashtab;
typedef uint32_t stage2_idx_item; /* 26 bits: 8 bits = left bucket index
9 bits = left item index
9 bits = right item index */
typedef struct stage2_idx_bucket {
stage2_idx_item items[COARSE_BUCKET_ITEMS];
} stage2_idx_bucket;
typedef struct stage2_idx_hashtab {
uint16_t counts[NUM_COARSE_BUCKETS];
stage2_idx_bucket buckets[NUM_COARSE_BUCKETS];
} stage2_idx_hashtab;
#ifdef SOLVER_PACKED_STAGE2
#pragma pack(push, 1)
typedef struct stage2_data_item {
uint32_t upper; /* 22 bits */
uint8_t middle; /* 8 bits */
uint8_t lower; /* 7 bits */
} stage2_data_item;
#pragma pack(pop)
#else
typedef uint64_t stage2_data_item; /* 37 bits */
#endif
typedef struct stage2_data_bucket {
stage2_data_item items[COARSE_BUCKET_ITEMS];
} stage2_data_bucket;
typedef struct stage2_data_hashtab {
stage2_data_bucket buckets[NUM_COARSE_BUCKETS];
} stage2_data_hashtab;
typedef uint32_t stage3_data_item; /* 22 bits */
typedef struct stage3_data_bucket {
stage3_data_item items[COARSE_BUCKET_ITEMS];
} stage3_data_bucket;
typedef struct stage3_data_hashtab {
stage3_data_bucket buckets[NUM_COARSE_BUCKETS];
} stage3_data_hashtab;
typedef stage2_idx_hashtab stage3_idx_hashtab;
typedef stage2_idx_item stage3_idx_item;
typedef struct solver_heap {
stage1_idx_hashtab stage1_indices; /* 172 544 bytes */
stage2_idx_hashtab stage2_indices; /* 344 576 bytes */
stage2_data_hashtab stage2_data; /* 688 128 bytes */
union {
stage1_data_hashtab stage1_data; /* 688 128 bytes */
struct {
stage3_idx_hashtab stage3_indices; /* 344 576 bytes */
stage3_data_hashtab stage3_data; /* 344 064 bytes */
};
};
fine_hashtab scratch_ht; /* 3 200 bytes */
} solver_heap; /* TOTAL: 1 897 088 bytes */
#endif
|
