Root/meas.c

1/*
2 * meas.c - Measurements
3 *
4 * Written 2009, 2010, 2012 by Werner Almesberger
5 * Copyright 2009, 2010, 2012 by Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13
14#include <stdlib.h>
15
16#include "util.h"
17#include "coord.h"
18#include "expr.h"
19#include "obj.h"
20#include "inst.h"
21#include "meas.h"
22
23
24int n_samples;
25
26
27struct num eval_unit(const struct expr *expr, const struct frame *frame);
28
29
30void reset_samples(struct sample **samples, int n)
31{
32    struct sample *next;
33    int i;
34
35    for (i = 0; i != n; i++)
36        while (samples[i]) {
37            next = samples[i]->next;
38            bitset_free(samples[i]->frame_set);
39            free(samples[i]);
40            samples[i] = next;
41        }
42}
43
44
45void meas_start(void)
46{
47    const struct frame *frame;
48    struct vec *vec;
49
50    n_samples = 0;
51    for (frame = frames; frame; frame = frame->next)
52        for (vec = frame->vecs; vec; vec = vec->next)
53            vec->n = n_samples++;
54}
55
56
57void meas_post(const struct vec *vec, struct coord pos,
58    const struct bitset *frame_set)
59{
60    struct sample **walk, *new;
61
62    for (walk = &curr_pkg->samples[vec->n]; *walk; walk = &(*walk)->next) {
63        if (pos.y < (*walk)->pos.y)
64            break;
65        if (pos.y > (*walk)->pos.y)
66            continue;
67        if (pos.x < (*walk)->pos.x)
68            break;
69        if (pos.x != (*walk)->pos.x)
70            continue;
71        if (bitset_ge((*walk)->frame_set, frame_set))
72            return;
73        if (bitset_ge(frame_set, (*walk)->frame_set)) {
74            bitset_or((*walk)->frame_set, frame_set);
75            return;
76        }
77    }
78    new = alloc_type(struct sample);
79    new->pos = pos;
80    new->frame_set = bitset_clone(frame_set);
81    new->next = *walk;
82    *walk = new;
83}
84
85
86/* ----- lt operators ------------------------------------------------------ */
87
88
89int lt_x(struct coord a, struct coord b)
90{
91    return a.x < b.x;
92}
93
94
95int lt_y(struct coord a, struct coord b)
96{
97    return a.y < b.y;
98}
99
100
101int lt_xy(struct coord a, struct coord b)
102{
103    return a.y < b.y || (a.y == b.y && a.x < b.x);
104}
105
106
107/* ----- measurement type map ---------------------------------------------- */
108
109
110static lt_op_type lt_op[mt_n] = {
111    lt_xy,
112    lt_x,
113    lt_y,
114    lt_xy,
115    lt_x,
116    lt_y
117};
118
119
120static int is_next[mt_n] = {
121    1, 1, 1,
122    0, 0, 0
123};
124
125
126/* ----- search functions -------------------------------------------------- */
127
128
129static int closer(int da, int db)
130{
131    int abs_a, abs_b;
132
133    abs_a = da < 0 ? -da : da;
134    abs_b = db < 0 ? -db : db;
135    if (abs_a < abs_b)
136        return 1;
137    if (abs_a > abs_b)
138        return 0;
139    /*
140     * Really *all* other things being equal, pick the one that protrudes
141     * in the positive direction.
142     */
143    return da > db;
144}
145
146
147static int better_next(lt_op_type lt,
148    struct coord a0, struct coord b0, struct coord b)
149{
150    /* if we don't have any suitable point A0 < B0 yet, use this one */
151    if (!lt(a0, b0))
152        return 1;
153
154    /* B must be strictly greater than A0 */
155    if (!lt(a0, b))
156        return 0;
157
158    /* if we can get closer to A0, do so */
159    if (lt(b, b0))
160        return 1;
161
162    /* reject B > B0 */
163    if (lt(b0, b))
164        return 0;
165
166    /*
167     * B == B0 along the coordinate we measure. Now give the other
168     * coordinate a chance. This gives us a stable sort order and it
169     * makes meas/measx/measy usually select the same point.
170     */
171    if (lt == lt_xy)
172        return 0;
173    if (lt == lt_x)
174        return closer(b.y-a0.y, b0.y-a0.y);
175    if (lt == lt_y)
176        return closer(b.x-a0.x, b0.x-a0.x);
177    abort();
178}
179
180
181/*
182 * In order to obtain a stable order, we sort points equal on the measured
183 * coordinate also by xy:
184 *
185 * if (*a < a0) use *a
186 * else if (*a == a0 && *a <xy a0) use *a
187 */
188
189const struct sample *meas_find_min(lt_op_type lt, const struct sample *s,
190    const struct bitset *qual)
191{
192    const struct sample *min = NULL;
193
194    while (s) {
195        if (!qual || bitset_ge(s->frame_set, qual))
196            if (!min || lt(s->pos, min->pos) ||
197                (!lt(min->pos, s->pos) && lt_xy(s->pos, min->pos)))
198                min = s;
199        s = s->next;
200    }
201    return min;
202}
203
204
205const struct sample *meas_find_next(lt_op_type lt, const struct sample *s,
206    struct coord ref, const struct bitset *qual)
207{
208    const struct sample *next = NULL;
209
210    while (s) {
211        if (!qual || bitset_ge(s->frame_set, qual))
212            if (!next || better_next(lt, ref, next->pos, s->pos))
213                next = s;
214        s = s->next;
215    }
216    return next;
217}
218
219
220const struct sample *meas_find_max(lt_op_type lt, const struct sample *s,
221    const struct bitset *qual)
222{
223    const struct sample *max = NULL;
224
225    while (s) {
226        if (!qual || bitset_ge(s->frame_set, qual))
227            if (!max || lt(max->pos, s->pos) ||
228                (!lt(s->pos, max->pos) && lt_xy(max->pos, s->pos)))
229                max = s;
230        s = s->next;
231    }
232    return max;
233}
234
235
236/* ----- instantiation ----------------------------------------------------- */
237
238
239static struct bitset *make_frame_set(struct frame_qual *qual, int n_frames)
240{
241    struct bitset *set;
242
243    set = bitset_new(n_frames);
244    while (qual) {
245        bitset_set(set, qual->frame->n);
246        qual = qual->next;
247    }
248    return set;
249}
250
251
252static int instantiate_meas_pkg(int n_frames)
253{
254    struct obj *obj;
255    const struct meas *meas;
256    struct bitset *set;
257    const struct sample *a0, *b0;
258    lt_op_type lt;
259
260    for (obj = frames->objs; obj; obj = obj->next) {
261        if (obj->type != ot_meas)
262            continue;
263        meas = &obj->u.meas;
264
265        /* optimization. not really needed anymore. */
266        if (!curr_pkg->samples[obj->base->n] ||
267            !curr_pkg->samples[meas->high->n])
268            continue;
269
270        lt = lt_op[meas->type];
271
272        set = make_frame_set(meas->low_qual, n_frames);
273        a0 = meas_find_min(lt, curr_pkg->samples[obj->base->n], set);
274        bitset_free(set);
275        if (!a0)
276            continue;
277
278        set = make_frame_set(meas->high_qual, n_frames);
279        if (is_next[meas->type])
280            b0 = meas_find_next(lt,
281                curr_pkg->samples[meas->high->n], a0->pos, set);
282        else
283            b0 = meas_find_max(lt,
284                curr_pkg->samples[meas->high->n], set);
285        bitset_free(set);
286        if (!b0)
287            continue;
288
289        inst_meas(obj,
290            meas->inverted ? b0->pos : a0->pos,
291            meas->inverted ? a0->pos : b0->pos);
292    }
293    return 1;
294}
295
296
297static void purge_meas(struct pkg *pkg)
298{
299    struct inst **anchor, *inst;
300
301    anchor = pkg->insts+ip_meas;
302    while (*anchor)
303        if ((*anchor)->u.meas.valid) {
304            anchor = &(*anchor)->next;
305        } else {
306            inst = *anchor;
307            *anchor = inst->next;
308            free(inst);
309        }
310}
311
312
313int instantiate_meas(int n_frames)
314{
315    struct pkg *pkg;
316
317    frame_instantiating = pkgs->insts[ip_frame];
318    for (pkg = pkgs; pkg; pkg = pkg->next)
319        if (pkg->name) {
320            inst_select_pkg(pkg->name, 0);
321            if (!instantiate_meas_pkg(n_frames))
322                return 0;
323            purge_meas(pkg);
324        }
325    return 1;
326}
327

Archive Download this file

Branches:
master



interactive