1 #include "config.h"
2 #include "types.h"
3
4 #if (defined(__AVX512F__) && defined(__AVX512DQ__)) || defined(__AVX2__)
5 #include <immintrin.h>
6 #endif
7
8 u32 skim(const u64 *virgin, const u64 *current, const u64 *current_end);
9 u64 classify_word(u64 word);
10
classify_word(u64 word)11 inline u64 classify_word(u64 word) {
12
13 u16 mem16[4];
14 memcpy(mem16, &word, sizeof(mem16));
15
16 mem16[0] = count_class_lookup16[mem16[0]];
17 mem16[1] = count_class_lookup16[mem16[1]];
18 mem16[2] = count_class_lookup16[mem16[2]];
19 mem16[3] = count_class_lookup16[mem16[3]];
20
21 memcpy(&word, mem16, sizeof(mem16));
22 return word;
23
24 }
25
simplify_trace(afl_state_t * afl,u8 * bytes)26 void simplify_trace(afl_state_t *afl, u8 *bytes) {
27
28 u64 *mem = (u64 *)bytes;
29 u32 i = (afl->fsrv.map_size >> 3);
30
31 while (i--) {
32
33 /* Optimize for sparse bitmaps. */
34
35 if (unlikely(*mem)) {
36
37 u8 *mem8 = (u8 *)mem;
38
39 mem8[0] = simplify_lookup[mem8[0]];
40 mem8[1] = simplify_lookup[mem8[1]];
41 mem8[2] = simplify_lookup[mem8[2]];
42 mem8[3] = simplify_lookup[mem8[3]];
43 mem8[4] = simplify_lookup[mem8[4]];
44 mem8[5] = simplify_lookup[mem8[5]];
45 mem8[6] = simplify_lookup[mem8[6]];
46 mem8[7] = simplify_lookup[mem8[7]];
47
48 } else
49
50 *mem = 0x0101010101010101ULL;
51
52 mem++;
53
54 }
55
56 }
57
classify_counts(afl_forkserver_t * fsrv)58 inline void classify_counts(afl_forkserver_t *fsrv) {
59
60 u64 *mem = (u64 *)fsrv->trace_bits;
61 u32 i = (fsrv->map_size >> 3);
62
63 while (i--) {
64
65 /* Optimize for sparse bitmaps. */
66
67 if (unlikely(*mem)) { *mem = classify_word(*mem); }
68
69 mem++;
70
71 }
72
73 }
74
75 /* Updates the virgin bits, then reflects whether a new count or a new tuple is
76 * seen in ret. */
discover_word(u8 * ret,u64 * current,u64 * virgin)77 inline void discover_word(u8 *ret, u64 *current, u64 *virgin) {
78
79 /* Optimize for (*current & *virgin) == 0 - i.e., no bits in current bitmap
80 that have not been already cleared from the virgin map - since this will
81 almost always be the case. */
82
83 if (*current & *virgin) {
84
85 if (likely(*ret < 2)) {
86
87 u8 *cur = (u8 *)current;
88 u8 *vir = (u8 *)virgin;
89
90 /* Looks like we have not found any new bytes yet; see if any non-zero
91 bytes in current[] are pristine in virgin[]. */
92
93 if ((cur[0] && vir[0] == 0xff) || (cur[1] && vir[1] == 0xff) ||
94 (cur[2] && vir[2] == 0xff) || (cur[3] && vir[3] == 0xff) ||
95 (cur[4] && vir[4] == 0xff) || (cur[5] && vir[5] == 0xff) ||
96 (cur[6] && vir[6] == 0xff) || (cur[7] && vir[7] == 0xff))
97 *ret = 2;
98 else
99 *ret = 1;
100
101 }
102
103 *virgin &= ~*current;
104
105 }
106
107 }
108
109 #if defined(__AVX512F__) && defined(__AVX512DQ__)
110 #define PACK_SIZE 64
skim(const u64 * virgin,const u64 * current,const u64 * current_end)111 inline u32 skim(const u64 *virgin, const u64 *current, const u64 *current_end) {
112
113 for (; current != current_end; virgin += 8, current += 8) {
114
115 __m512i value = *(__m512i *)current;
116 __mmask8 mask = _mm512_testn_epi64_mask(value, value);
117
118 /* All bytes are zero. */
119 if (likely(mask == 0xff)) continue;
120
121 /* Look for nonzero bytes and check for new bits. */
122 #define UNROLL(x) \
123 if (unlikely(!(mask & (1 << x)) && classify_word(current[x]) & virgin[x])) \
124 return 1
125 UNROLL(0);
126 UNROLL(1);
127 UNROLL(2);
128 UNROLL(3);
129 UNROLL(4);
130 UNROLL(5);
131 UNROLL(6);
132 UNROLL(7);
133 #undef UNROLL
134
135 }
136
137 return 0;
138
139 }
140
141 #endif
142
143 #if !defined(PACK_SIZE) && defined(__AVX2__)
144 #define PACK_SIZE 32
skim(const u64 * virgin,const u64 * current,const u64 * current_end)145 inline u32 skim(const u64 *virgin, const u64 *current, const u64 *current_end) {
146
147 __m256i zeroes = _mm256_setzero_si256();
148
149 for (; current < current_end; virgin += 4, current += 4) {
150
151 __m256i value = *(__m256i *)current;
152 __m256i cmp = _mm256_cmpeq_epi64(value, zeroes);
153 u32 mask = _mm256_movemask_epi8(cmp);
154
155 /* All bytes are zero. */
156 if (likely(mask == (u32)-1)) continue;
157
158 /* Look for nonzero bytes and check for new bits. */
159 if (unlikely(!(mask & 0xff) && classify_word(current[0]) & virgin[0]))
160 return 1;
161 if (unlikely(!(mask & 0xff00) && classify_word(current[1]) & virgin[1]))
162 return 1;
163 if (unlikely(!(mask & 0xff0000) && classify_word(current[2]) & virgin[2]))
164 return 1;
165 if (unlikely(!(mask & 0xff000000) && classify_word(current[3]) & virgin[3]))
166 return 1;
167
168 }
169
170 return 0;
171
172 }
173
174 #endif
175
176 #if !defined(PACK_SIZE)
177 #define PACK_SIZE 32
skim(const u64 * virgin,const u64 * current,const u64 * current_end)178 inline u32 skim(const u64 *virgin, const u64 *current, const u64 *current_end) {
179
180 for (; current < current_end; virgin += 4, current += 4) {
181
182 if (unlikely(current[0] && classify_word(current[0]) & virgin[0])) return 1;
183 if (unlikely(current[1] && classify_word(current[1]) & virgin[1])) return 1;
184 if (unlikely(current[2] && classify_word(current[2]) & virgin[2])) return 1;
185 if (unlikely(current[3] && classify_word(current[3]) & virgin[3])) return 1;
186
187 }
188
189 return 0;
190
191 }
192
193 #endif
194
195