1 /* $Id: recode-conds.c,v 1.2 2008/07/01 01:39:01 fredette Exp $ */
2
3 /* libtme/recode-conds.c - generic support for recode conditions: */
4
5 /*
6 * Copyright (c) 2008 Matt Fredette
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by Matt Fredette.
20 * 4. The name of the author may not be used to endorse or promote products
21 * derived from this software without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
25 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
27 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
28 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
29 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
31 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #include <tme/common.h>
37 _TME_RCSID("$Id: recode-conds.c,v 1.2 2008/07/01 01:39:01 fredette Exp $");
38
39 #if TME_HAVE_RECODE
40
41 /* includes: */
42 #include "recode-impl.h"
43
44 /* this returns a conditions thunk for a conditions group: */
45 const struct tme_recode_conds_thunk *
tme_recode_conds_thunk(struct tme_recode_ic * ic,const struct tme_recode_conds_group * conds_group_template)46 tme_recode_conds_thunk(struct tme_recode_ic *ic,
47 const struct tme_recode_conds_group *conds_group_template)
48 {
49 const struct tme_recode_conds_group *conds_group_other;
50 struct tme_recode_conds_group *conds_group;
51
52 /* loop over the existing conditions groups: */
53 for (conds_group_other = ic->tme_recode_ic_conds_groups;
54 conds_group_other != NULL;
55 conds_group_other = conds_group_other->tme_recode_conds_group_next) {
56
57 /* skip this existing conditions group if its flags register
58 size or index or flags don't match: */
59 if (conds_group_other->tme_recode_conds_group_flags_reg_size
60 != conds_group_template->tme_recode_conds_group_flags_reg_size) {
61 continue;
62 }
63 if (conds_group_other->tme_recode_conds_group_flags_reg
64 != conds_group_template->tme_recode_conds_group_flags_reg) {
65 continue;
66 }
67 if (conds_group_other->tme_recode_conds_group_flags
68 != conds_group_template->tme_recode_conds_group_flags) {
69 continue;
70 }
71
72 /* skip this existing conditions group if its conditions count or
73 guest function don't match: */
74 if (conds_group_other->tme_recode_conds_group_cond_count
75 != conds_group_template->tme_recode_conds_group_cond_count) {
76 continue;
77 }
78 if (conds_group_other->tme_recode_conds_group_guest_func
79 != conds_group_template->tme_recode_conds_group_guest_func) {
80 continue;
81 }
82
83 /* return the conditions thunk from the existing conditions
84 group: */
85 return (conds_group_other->tme_recode_conds_group_thunk);
86 }
87
88 /* allocate and fill the new conditions group: */
89 conds_group = tme_new0(struct tme_recode_conds_group, 1);
90 *conds_group = *conds_group_template;
91
92 /* build the new conditions thunk: */
93 conds_group->tme_recode_conds_group_thunk = tme_recode_host_conds_thunk_new(ic, conds_group);
94
95 /* add this new conditions group to the ic: */
96 conds_group->tme_recode_conds_group_next = ic->tme_recode_ic_conds_groups;
97 ic->tme_recode_ic_conds_groups = conds_group;
98
99 /* update the initial thunk offset of the first variable thunk: */
100 ic->tme_recode_ic_thunk_off_variable
101 = tme_recode_build_to_thunk_off(ic, ic->tme_recode_ic_thunk_build_next);
102
103 /* return the conditions thunk: */
104 return (conds_group->tme_recode_conds_group_thunk);
105 }
106
107 /* this generic function returns the maximum index for a conditions
108 group's flags: */
109 tme_uint32_t
tme_recode_conds_group_flags_index_max(const struct tme_recode_conds_group * conds_group)110 tme_recode_conds_group_flags_index_max(const struct tme_recode_conds_group *conds_group)
111 {
112 tme_recode_uguest_t conds_group_flags_mask;
113 unsigned int count_bits;
114
115 /* count the number of bits in the condition group flags mask: */
116 conds_group_flags_mask = conds_group->tme_recode_conds_group_flags;
117 assert (conds_group_flags_mask != 0);
118 for (count_bits = 0;
119 conds_group_flags_mask != 0;
120 count_bits++) {
121 conds_group_flags_mask &= (conds_group_flags_mask - 1);
122 }
123
124 /* return the maximum condition group flags index: */
125 assert (count_bits <= (sizeof(tme_uint32_t) * 8));
126 return ((((tme_uint32_t) 2) << (count_bits - 1)) - 1);
127 }
128
129 /* this generic function returns the indexed combination of a
130 conditions group's flags: */
131 tme_recode_uguest_t
tme_recode_conds_group_flags_from_index(const struct tme_recode_conds_group * conds_group,tme_uint32_t conds_group_flags_index)132 tme_recode_conds_group_flags_from_index(const struct tme_recode_conds_group *conds_group,
133 tme_uint32_t conds_group_flags_index)
134 {
135 tme_recode_uguest_t conds_group_flags_mask;
136 tme_recode_uguest_t conds_group_flags;
137 tme_recode_uguest_t conds_group_flag_next;
138
139 /* make this combination of the flags: */
140 conds_group_flags_mask = conds_group->tme_recode_conds_group_flags;
141 conds_group_flags = 0;
142 conds_group_flag_next = 1;
143 do {
144 if (conds_group_flags_mask & conds_group_flag_next) {
145 if (conds_group_flags_index & 1) {
146 conds_group_flags |= conds_group_flag_next;
147 }
148 conds_group_flags_index >>= 1;
149 }
150 conds_group_flag_next <<= 1;
151 } while (conds_group_flags_index != 0);
152 return (conds_group_flags);
153 }
154
155 /* this generic function returns a simple mask of a conditions group's
156 flags and one or more bitwise operations that can be used with the
157 mask to test the given condition. it returns zero if the condition
158 can't be tested with a simple mask: */
159 tme_uint32_t
tme_recode_conds_simple_mask(const struct tme_recode_conds_group * conds_group,tme_uint32_t cond,tme_recode_uguest_t * _conds_group_flags_mask)160 tme_recode_conds_simple_mask(const struct tme_recode_conds_group *conds_group,
161 tme_uint32_t cond,
162 tme_recode_uguest_t *_conds_group_flags_mask)
163 {
164 tme_recode_uguest_t conds_group_flags_same_for_mask[2];
165 int conds_group_flags_same_for_defined[2];
166 tme_uint32_t conds_group_flags_index;
167 tme_recode_uguest_t conds_group_flags;
168 int cond_true;
169 tme_recode_uguest_t conds_group_flags_same_for[2];
170 tme_recode_uguest_t conds_group_flags_mask;
171 tme_uint32_t bitwise_mask;
172
173 /* we haven't seen any combination of flags that make the condition
174 either true or false yet: */
175 conds_group_flags_same_for_mask[1] = conds_group->tme_recode_conds_group_flags;
176 conds_group_flags_same_for_mask[0] = conds_group->tme_recode_conds_group_flags;
177 conds_group_flags_same_for_defined[1] = FALSE;
178 conds_group_flags_same_for_defined[0] = FALSE;
179
180 /* loop over all combinations of the flags: */
181 conds_group_flags_index = tme_recode_conds_group_flags_index_max(conds_group);
182 do {
183 conds_group_flags = tme_recode_conds_group_flags_from_index(conds_group, conds_group_flags_index);
184
185 /* test if this combination of flags makes the condition true: */
186 cond_true = ((*conds_group->tme_recode_conds_group_guest_func)(conds_group_flags, cond) != 0);
187
188 /* if this is the first combination of flags that we have seen
189 that makes the condition have this state: */
190 if (!conds_group_flags_same_for_defined[cond_true]) {
191
192 /* start tracking flags that always have the same values when
193 the condition has this state: */
194 conds_group_flags_same_for[cond_true] = conds_group_flags;
195 conds_group_flags_same_for_defined[cond_true] = TRUE;
196 }
197
198 /* otherwise, this is not the first combination of flags that
199 we have seen that makes the condition have this state: */
200 else {
201
202 /* drop any flags that before had the same value when the
203 condition had this state, that now have a different value
204 when the condition has this same state: */
205 conds_group_flags_same_for_mask[cond_true]
206 &= ~(conds_group_flags_same_for[cond_true]
207 ^ conds_group_flags);
208 }
209
210 } while (conds_group_flags_index-- != 0);
211
212 /* if we never saw a combination of flags that makes the condition
213 true: */
214 if (!conds_group_flags_same_for_defined[1]) {
215
216 /* this condition is always false, which we can express with an
217 all-bits-zero mask and either OR or AND: */
218 *_conds_group_flags_mask = 0;
219 return (TME_RECODE_BITWISE_OR | TME_RECODE_BITWISE_AND);
220 }
221
222 /* if we never saw a combination of flags that makes the condition
223 false: */
224 if (!conds_group_flags_same_for_defined[0]) {
225
226 /* this condition is always true, which we can express with an
227 all-bits-zero mask and either NOR or NAND: */
228 *_conds_group_flags_mask = 0;
229 return (TME_RECODE_BITWISE_NOR | TME_RECODE_BITWISE_NAND);
230 }
231
232 /* bits that are the same in all combinations of flags that make the
233 condition both true and false, can't be in the mask of flags that
234 determine the condition: */
235 conds_group_flags_mask
236 = ((conds_group_flags_same_for[1]
237 ^ ~conds_group_flags_same_for[0])
238 & conds_group_flags_same_for_mask[1]
239 & conds_group_flags_same_for_mask[0]);
240 conds_group_flags_same_for_mask[1] &= ~conds_group_flags_mask;
241 conds_group_flags_same_for_mask[0] &= ~conds_group_flags_mask;
242
243 /* if there is any mask of flags that determine one state of the
244 condition, the mask of flags that determine the other state must
245 either be zero, or be exactly the same mask: */
246 conds_group_flags_mask = conds_group_flags_same_for_mask[1];
247 if (conds_group_flags_mask == 0) {
248 conds_group_flags_mask = conds_group_flags_same_for_mask[0];
249 }
250 else {
251 assert (conds_group_flags_same_for_mask[0] == 0
252 || conds_group_flags_same_for_mask[0] == conds_group_flags_mask);
253 }
254
255 /* loop over all combinations of the flags again, eliminating
256 bitwise operations that don't give the correct condition state
257 under the mask for all combinations: */
258 bitwise_mask
259 = (TME_RECODE_BITWISE_OR
260 | TME_RECODE_BITWISE_NOR
261 | TME_RECODE_BITWISE_AND
262 | TME_RECODE_BITWISE_NAND);
263 conds_group_flags_index = tme_recode_conds_group_flags_index_max(conds_group);
264 do {
265 conds_group_flags = tme_recode_conds_group_flags_from_index(conds_group, conds_group_flags_index);
266
267 /* test if this combination of flags makes the condition true: */
268 cond_true = ((*conds_group->tme_recode_conds_group_guest_func)(conds_group_flags, cond) != 0);
269
270 /* mask off all other flags: */
271 conds_group_flags &= conds_group_flags_mask;
272
273 /* eliminate bitwise operations that don't give the correct
274 condition state for the flags: */
275 if (cond_true != (conds_group_flags != 0)) {
276 bitwise_mask &= ~TME_RECODE_BITWISE_OR;
277 }
278 if (cond_true != (conds_group_flags == 0)) {
279 bitwise_mask &= ~TME_RECODE_BITWISE_NOR;
280 }
281 if (cond_true != (conds_group_flags == conds_group_flags_mask)) {
282 bitwise_mask &= ~TME_RECODE_BITWISE_AND;
283 }
284 if (cond_true != (conds_group_flags != conds_group_flags_mask)) {
285 bitwise_mask &= ~TME_RECODE_BITWISE_NAND;
286 }
287
288 } while (conds_group_flags_index-- != 0);
289
290 /* return any mask of flags and bitwise operations: */
291 *_conds_group_flags_mask = conds_group_flags_mask;
292 return (bitwise_mask);
293 }
294
295 #ifdef TME_RECODE_DEBUG
296 #include <stdio.h>
297
298 /* this function dumps a conditions thunk: */
299 void
tme_recode_conds_thunk_dump(const struct tme_recode_ic * ic,const struct tme_recode_conds_thunk * conds_thunk,const char * const * cond_names)300 tme_recode_conds_thunk_dump(const struct tme_recode_ic *ic,
301 const struct tme_recode_conds_thunk *conds_thunk,
302 const char * const *cond_names)
303 {
304 printf(" flags offset: 0x%x\n flags tested: ",
305 (unsigned int) conds_thunk->tme_recode_conds_thunk_flags_offset);
306 tme_recode_uguest_dump(conds_thunk->tme_recode_conds_thunk_flags);
307 printf("\n");
308 tme_recode_host_conds_thunk_dump(ic, conds_thunk, cond_names);
309 }
310 #endif /* TME_RECODE_DEBUG */
311
312 #endif /* TME_HAVE_RECODE */
313