src
bitmap.cc
Go to the documentation of this file.
1 #include <algorithm> // min
2 #include <string.h> // memset
3 
4 #include "src/codegen/bitmap.h"
5 #include "src/codegen/go.h"
6 #include "src/codegen/output.h"
7 #include "src/conf/opt.h"
8 #include "src/globals.h"
9 
10 namespace re2c
11 {
12 
13 BitMap *BitMap::first = NULL;
14 
15 BitMap::BitMap(const Go *g, const State *x)
16  : go(g)
17  , on(x)
18  , next(first)
19  , i(0)
20  , m(0)
21 {
22  first = this;
23 }
24 
26 {
27  delete next;
28 }
29 
30 const BitMap *BitMap::find(const Go *g, const State *x)
31 {
32  for (const BitMap *b = first; b; b = b->next)
33  {
34  if (matches(b->go->span, b->go->nSpans, b->on, g->span, g->nSpans, x))
35  {
36  return b;
37  }
38  }
39 
40  return new BitMap(g, x);
41 }
42 
43 const BitMap *BitMap::find(const State *x)
44 {
45  for (const BitMap *b = first; b; b = b->next)
46  {
47  if (b->on == x)
48  {
49  return b;
50  }
51  }
52 
53  return NULL;
54 }
55 
56 static void doGen(const Go *g, const State *s, uint32_t *bm, uint32_t f, uint32_t m)
57 {
58  Span *b = g->span, *e = &b[g->nSpans];
59  uint32_t lb = 0;
60 
61  for (; b < e; ++b)
62  {
63  if (b->to == s)
64  {
65  for (; lb < b->ub && lb < 256; ++lb)
66  {
67  bm[lb-f] |= m;
68  }
69  }
70 
71  lb = b->ub;
72  }
73 }
74 
75 void BitMap::gen(OutputFile & o, uint32_t ind, uint32_t lb, uint32_t ub)
76 {
77  if (first && bUsedYYBitmap)
78  {
79  o.wind(ind).ws("static const unsigned char ").wstring(opts->yybm).ws("[] = {");
80 
81  uint32_t c = 1, n = ub - lb;
82  const BitMap *cb = first;
83 
84  while((cb = cb->next) != NULL) {
85  ++c;
86  }
87  BitMap *b = first;
88 
89  uint32_t *bm = new uint32_t[n];
90 
91  for (uint32_t i = 0, t = 1; b; i += n, t += 8)
92  {
93  memset(bm, 0, n * sizeof(uint32_t));
94 
95  for (uint32_t m = 0x80; b && m; m >>= 1)
96  {
97  b->i = i;
98  b->m = m;
99  doGen(b->go, b->on, bm, lb, m);
100  b = const_cast<BitMap*>(b->next);
101  }
102 
103  if (c > 8)
104  {
105  o.ws("\n").wind(ind+1).ws("/* table ").wu32(t).ws(" .. ").wu32(std::min(c, t+7)).ws(": ").wu32(i).ws(" */");
106  }
107 
108  for (uint32_t j = 0; j < n; ++j)
109  {
110  if (j % 8 == 0)
111  {
112  o.ws("\n").wind(ind+1);
113  }
114 
115  if (opts->yybmHexTable)
116  {
117  o.wu32_hex(bm[j]);
118  }
119  else
120  {
121  o.wu32_width(bm[j], 3);
122  }
123  o.ws(", ");
124  }
125  }
126 
127  o.ws("\n").wind(ind).ws("};\n");
128 
129  delete[] bm;
130  }
131 }
132 
133 // All spans in b1 that lead to s1 are pairwise equal to that in b2 leading to s2
134 bool matches(const Span * b1, uint32_t n1, const State * s1, const Span * b2, uint32_t n2, const State * s2)
135 {
136  const Span * e1 = &b1[n1];
137  uint32_t lb1 = 0;
138  const Span * e2 = &b2[n2];
139  uint32_t lb2 = 0;
140 
141  for (;;)
142  {
143  for (; b1 < e1 && b1->to != s1; ++b1)
144  {
145  lb1 = b1->ub;
146  }
147  for (; b2 < e2 && b2->to != s2; ++b2)
148  {
149  lb2 = b2->ub;
150  }
151  if (b1 == e1)
152  {
153  return b2 == e2;
154  }
155  if (b2 == e2)
156  {
157  return false;
158  }
159  if (lb1 != lb2 || b1->ub != b2->ub)
160  {
161  return false;
162  }
163  ++b1;
164  ++b2;
165  }
166 }
167 
168 } // end namespace re2c
const State * on
Definition: bitmap.h:22
uint32_t nSpans
Definition: go.h:174
uint32_t ub
Definition: go.h:21
static void gen(OutputFile &, uint32_t ind, uint32_t, uint32_t)
Definition: bitmap.cc:75
OutputFile & ws(const char *s)
Definition: output.cc:173
OutputFile & wu32(uint32_t n)
Definition: output.cc:155
std::string yybm
Definition: opt.h:118
OutputFile & wind(uint32_t ind)
Definition: output.cc:191
const BitMap * next
Definition: bitmap.h:23
State * to
Definition: go.h:22
bool bUsedYYBitmap
Definition: main.cc:16
uint32_t m
Definition: bitmap.h:25
uint32_t i
Definition: bitmap.h:24
BitMap(const Go *, const State *)
Definition: bitmap.cc:15
const Go * go
Definition: bitmap.h:21
Opt opts
Definition: opt.cc:7
static void doGen(const Go *g, const State *s, uint32_t *bm, uint32_t f, uint32_t m)
Definition: bitmap.cc:56
static BitMap * first
Definition: bitmap.h:19
static const BitMap * find(const Go *, const State *)
Definition: bitmap.cc:30
bool yybmHexTable
Definition: opt.h:118
OutputFile & wu32_hex(uint32_t n)
Definition: output.cc:102
Span * span
Definition: go.h:175
bool matches(const Span *b1, uint32_t n1, const State *s1, const Span *b2, uint32_t n2, const State *s2)
Definition: bitmap.cc:134
OutputFile & wu32_width(uint32_t n, int w)
Definition: output.cc:120
Definition: bitmap.cc:10
Definition: go.h:19
OutputFile & wstring(const std::string &s)
Definition: output.cc:167
Definition: go.h:172