1 /* $NetBSD: fields.c,v 1.31 2009/11/06 18:34:22 joerg Exp $ */
4 * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Ben Harris and Jaromir Dolecek.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
34 * The Regents of the University of California. All rights reserved.
36 * This code is derived from software contributed to Berkeley by
39 * Redistribution and use in source and binary forms, with or without
40 * modification, are permitted provided that the following conditions
42 * 1. Redistributions of source code must retain the above copyright
43 * notice, this list of conditions and the following disclaimer.
44 * 2. Redistributions in binary form must reproduce the above copyright
45 * notice, this list of conditions and the following disclaimer in the
46 * documentation and/or other materials provided with the distribution.
47 * 3. Neither the name of the University nor the names of its contributors
48 * may be used to endorse or promote products derived from this software
49 * without specific prior written permission.
51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
52 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
53 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
54 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
55 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
56 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
57 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
59 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
60 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
64 /* Subroutines to generate sort keys. */
68 __RCSID("$NetBSD: fields.c,v 1.31 2009/11/06 18:34:22 joerg Exp $");
70 #define SKIP_BLANKS(ptr) { \
71 if (BLANK & d_mask[*(ptr)]) \
72 while (BLANK & d_mask[*(++(ptr))]); \
75 #define NEXTCOL(pos) { \
77 while (BLANK & l_d_mask[*(++pos)]); \
78 while ((*(pos+1) != '\0') && !((FLD_D | REC_D_F) & l_d_mask[*++pos]));\
81 static u_char *enterfield(u_char *, const u_char *, struct field *, int);
82 static u_char *number(u_char *, const u_char *, u_char *, u_char *, int);
83 static u_char *length(u_char *, const u_char *, u_char *, u_char *, int);
85 #define DECIMAL_POINT '.'
88 * constructs sort key with leading recheader, followed by the key,
89 * followed by the original line.
92 enterkey(RECHEADER *keybuf, const u_char *keybuf_end, u_char *line_data,
93 size_t line_size, struct field fieldtable[])
94 /* keybuf: pointer to start of key */
98 u_char *lineend, *pos;
101 struct coldesc *clpos;
107 lineend = line_data + line_size-1;
108 /* don't include rec_delimiter */
110 for (i = 0; i < ncols; i++) {
112 for (; (col < clpos->num) && (pos < lineend); col++) {
117 clpos->start = SEP_FLAG ? pos + 1 : pos;
121 if (pos >= lineend) {
122 clpos->end = lineend;
127 for (; i <= ncols; i++)
128 clist[i].start = clist[i].end = lineend;
129 if (clist[0].start < line_data)
133 * We write the sort keys (concatenated) followed by the
134 * original line data (for output) as the 'keybuf' data.
135 * keybuf->length is the number of key bytes + data bytes.
136 * keybuf->offset is the number of key bytes.
137 * We add a record separator weight after the key in case
138 * (as is usual) we need to preserve the order of equal lines,
140 * The key itself will have had the correct weight applied.
142 keypos = keybuf->data;
143 endkey = keybuf_end - line_size - 1;
144 if (endkey <= keypos)
145 /* No room for any key bytes */
148 for (ftpos = fieldtable + 1; ftpos->icol.num; ftpos++) {
149 if ((keypos = enterfield(keypos, endkey, ftpos,
150 fieldtable->flags)) == NULL)
154 keybuf->offset = keypos - keybuf->data;
155 keybuf->length = keybuf->offset + line_size;
158 * Posix requires that equal keys be further sorted by the
159 * entire original record.
160 * NetBSD has (at least for some time) kept equal keys in
161 * their original order.
162 * For 'sort -u' posix_sort is unset.
164 keybuf->keylen = posix_sort ? keybuf->length : keybuf->offset;
166 memcpy(keypos, line_data, line_size);
171 * constructs a field (as defined by -k) within a key
174 enterfield(u_char *tablepos, const u_char *endkey, struct field *cur_fld,
175 int __attribute__ ((unused)) gflags)
177 u_char *start, *end, *lineend, *mask, *lweight;
178 struct column icol, tcol;
181 icol = cur_fld->icol;
182 tcol = cur_fld->tcol;
183 flags = cur_fld->flags;
184 start = icol.p->start;
185 lineend = clist[ncols].end;
188 start += icol.indent;
189 start = min(start, lineend);
199 end = min(end, lineend);
205 return length(tablepos, endkey, start, end, flags);
207 return number(tablepos, endkey, start, end, flags);
209 /* Bound check space - assuming nothing is skipped */
210 if (tablepos + (end - start) + 1 >= endkey)
213 mask = cur_fld->mask;
214 lweight = cur_fld->weights;
215 for (; start < end; start++) {
216 if (!mask || mask[*start]) {
217 *tablepos++ = lweight[*start];
220 /* Add extra byte (absent from lweight) to sort short keys correctly */
221 *tablepos++ = lweight[REC_D];
226 * Numbers are converted to a floating point format (exponent & mantissa)
227 * so that they compare correctly as sequence of unsigned bytes.
228 * Bytes 0x00 and 0xff are used to terminate positive and negative numbers
229 * to ensure that 0.123 sorts after 0.12 and -0.123 sorts before -0.12.
231 * The first byte contain the overall sign, exponent sign and some of the
232 * exponent. These have to be ordered (-ve value, decreasing exponent),
233 * zero, (+ve value, increasing exponent).
235 * The first byte is 0x80 for zero, 0xc0 for +ve with exponent 0.
236 * -ve values are the 1's compliments (so 0x7f isn't used!).
238 * This only leaves 63 byte values for +ve exponents - which isn't enough.
239 * The largest 4 exponent values are used to hold a byte count of the
240 * number of following bytes that contain 8 exponent bits per byte,
241 * This lets us sort exponents from -2^31 to +2^31.
243 * The mantissa is stored 2 digits per byte offset by 0x40, for negative
244 * numbers the order must be reversed (they are bit inverted).
246 * Reverse sorts are done by inverting the sign of the number.
248 #define MAX_EXP_ENC ((int)sizeof(int))
251 number(u_char *pos, const u_char *bufend, u_char *line, u_char *lineend,
267 /* Give ourselves space for the key terminator */
270 /* Ensure we have enough space for the exponent */
271 if (pos + 1 + MAX_EXP_ENC > bufend)
275 if (*line == '-') { /* set the sign */
279 /* eat initial zeroes */
280 for (; *line == '0' && line < lineend; line++)
283 /* calculate exponents */
284 if (*line == DECIMAL_POINT) {
285 /* Decimal fraction */
287 while (*++line == '0' && line < lineend)
290 /* Large (absolute) value, count digits */
291 for (tline = line; *tline >= '0' &&
292 *tline <= '9' && tline < lineend; tline++)
296 /* If the first/next character isn't a digit, value is zero */
297 if (*line < '1' || *line > '9' || line >= lineend) {
298 /* This may be "0", "0.00", "000" or "fubar" but sorts as 0 */
299 /* XXX what about NaN, NAN, inf and INF */
304 /* Maybe here we should allow for e+12 (etc) */
306 if (exponent < 0x40 - MAX_EXP_ENC && -exponent < 0x40 - MAX_EXP_ENC) {
307 /* Value ok for simple encoding */
308 /* exponent 0 is 0xc0 for +ve numbers and 0x40 for -ve ones */
310 *pos++ = negate ^ exponent;
312 /* Out or range for a single byte */
314 t = exponent > 0 ? exponent : -exponent;
315 /* Count how many 8-bit bytes are needed */
321 /* 'c' better be 0..3 here - but probably 0..1 */
322 /* Offset just outside valid range */
323 t = c + 0x40 - MAX_EXP_ENC;
326 *pos++ = negate ^ (t + 0xc0);
327 /* now add each byte, most significant first */
329 *pos++ = negate ^ (exponent >> (c * 8));
332 /* Finally add mantissa, 2 digits per byte */
333 for (last_nz_pos = pos; line < lineend; ) {
337 val = (ch - '0') * 10;
339 if (ch == DECIMAL_POINT && !had_dp) {
345 while (line < lineend) {
347 if (ch == DECIMAL_POINT && !had_dp) {
351 if (ch < '0' || ch > '9')
357 *pos++ = negate ^ (val + 0x40);
362 /* Add key terminator, deleting any trailing "00" */
363 *last_nz_pos++ = negate;
365 return (last_nz_pos);
369 length(u_char *pos, const u_char *bufend, u_char *line, u_char *lineend,
375 l = snprintf((char *)buf, sizeof(buf), "%td", lineend - line);
376 return number(pos, bufend, buf, buf + l, flag);