/* $NetBSD: fields.c,v 1.33 2013/01/20 10:12:58 apb Exp $ */ /*- * Copyright (c) 2000-2003 The NetBSD Foundation, Inc. * All rights reserved. * * This code is derived from software contributed to The NetBSD Foundation * by Ben Harris and Jaromir Dolecek. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ /*- * Copyright (c) 1993 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Peter McIlroy. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ /* Subroutines to generate sort keys. */ #include "sort.h" __RCSID("$NetBSD: fields.c,v 1.33 2013/01/20 10:12:58 apb Exp $"); #define SKIP_BLANKS(ptr) { \ if (BLANK & d_mask[*(ptr)]) \ while (BLANK & d_mask[*(++(ptr))]); \ } #define NEXTCOL(pos) { \ if (!SEP_FLAG) \ while (BLANK & l_d_mask[*(++pos)]); \ while ((*(pos+1) != '\0') && !((FLD_D | REC_D_F) & l_d_mask[*++pos]));\ } static u_char *enterfield(u_char *, const u_char *, struct field *, int); static u_char *number(u_char *, const u_char *, u_char *, u_char *, int); static u_char *length(u_char *, const u_char *, u_char *, u_char *, int); #define DECIMAL_POINT '.' /* * constructs sort key with leading recheader, followed by the key, * followed by the original line. */ length_t enterkey(RECHEADER *keybuf, const u_char *keybuf_end, u_char *line_data, size_t line_size, struct field fieldtable[]) /* keybuf: pointer to start of key */ { int i; u_char *l_d_mask; u_char *lineend, *pos; const u_char *endkey; u_char *keypos; struct coldesc *clpos; int col = 1; struct field *ftpos; l_d_mask = d_mask; pos = line_data - 1; lineend = line_data + line_size-1; /* don't include rec_delimiter */ for (i = 0; i < ncols; i++) { clpos = clist + i; for (; (col < clpos->num) && (pos < lineend); col++) { NEXTCOL(pos); } if (pos >= lineend) break; clpos->start = SEP_FLAG ? pos + 1 : pos; NEXTCOL(pos); clpos->end = pos; col++; if (pos >= lineend) { clpos->end = lineend; i++; break; } } for (; i <= ncols; i++) clist[i].start = clist[i].end = lineend; if (clist[0].start < line_data) clist[0].start++; /* * We write the sort keys (concatenated) followed by the * original line data (for output) as the 'keybuf' data. * keybuf->length is the number of key bytes + data bytes. * keybuf->offset is the number of key bytes. * We add a record separator weight after the key in case * (as is usual) we need to preserve the order of equal lines, * and for 'sort -u'. * The key itself will have had the correct weight applied. */ keypos = keybuf->data; endkey = keybuf_end - line_size - 1; if (endkey <= keypos) /* No room for any key bytes */ return 1; for (ftpos = fieldtable + 1; ftpos->icol.num; ftpos++) { if ((keypos = enterfield(keypos, endkey, ftpos, fieldtable->flags)) == NULL) return (1); } keybuf->offset = keypos - keybuf->data; keybuf->length = keybuf->offset + line_size; /* * Posix requires that equal keys be further sorted by the * entire original record. * NetBSD has (at least for some time) kept equal keys in * their original order. * For 'sort -u' posix_sort is unset. */ keybuf->keylen = posix_sort ? keybuf->length : keybuf->offset; memcpy(keypos, line_data, line_size); return (0); } /* * constructs a field (as defined by -k) within a key */ static u_char * enterfield(u_char *tablepos, const u_char *endkey, struct field *cur_fld, int gflags) { u_char *start, *end, *lineend, *mask, *lweight; struct column icol, tcol; u_int flags; icol = cur_fld->icol; tcol = cur_fld->tcol; flags = cur_fld->flags; start = icol.p->start; lineend = clist[ncols].end; if (flags & BI) SKIP_BLANKS(start); start += icol.indent; start = min(start, lineend); if (!tcol.num) end = lineend; else { if (tcol.indent) { end = tcol.p->start; if (flags & BT) SKIP_BLANKS(end); end += tcol.indent; end = min(end, lineend); } else end = tcol.p->end; } if (flags & L) return length(tablepos, endkey, start, end, flags); if (flags & N) return number(tablepos, endkey, start, end, flags); /* Bound check space - assuming nothing is skipped */ if (tablepos + (end - start) + 1 >= endkey) return NULL; mask = cur_fld->mask; lweight = cur_fld->weights; for (; start < end; start++) { if (!mask || mask[*start]) { *tablepos++ = lweight[*start]; } } /* Add extra byte (absent from lweight) to sort short keys correctly */ *tablepos++ = lweight[REC_D]; return tablepos; } /* * Numbers are converted to a floating point format (exponent & mantissa) * so that they compare correctly as sequence of unsigned bytes. * Bytes 0x00 and 0xff are used to terminate positive and negative numbers * to ensure that 0.123 sorts after 0.12 and -0.123 sorts before -0.12. * * The first byte contain the overall sign, exponent sign and some of the * exponent. These have to be ordered (-ve value, decreasing exponent), * zero, (+ve value, increasing exponent). * * The first byte is 0x80 for zero, 0xc0 for +ve with exponent 0. * -ve values are the 1's compliments (so 0x7f isn't used!). * * This only leaves 63 byte values for +ve exponents - which isn't enough. * The largest 4 exponent values are used to hold a byte count of the * number of following bytes that contain 8 exponent bits per byte, * This lets us sort exponents from -2^31 to +2^31. * * The mantissa is stored 2 digits per byte offset by 0x40, for negative * numbers the order must be reversed (they are bit inverted). * * Reverse sorts are done by inverting the sign of the number. */ #define MAX_EXP_ENC ((int)sizeof(int)) static u_char * number(u_char *pos, const u_char *bufend, u_char *line, u_char *lineend, int reverse) { int exponent = -1; int had_dp = 0; u_char *tline; char ch; unsigned int val; u_char *last_nz_pos; u_char negate; if (reverse & R) negate = 0xff; else negate = 0; /* Give ourselves space for the key terminator */ bufend--; /* Ensure we have enough space for the exponent */ if (pos + 1 + MAX_EXP_ENC > bufend) return (NULL); SKIP_BLANKS(line); if (*line == '-') { /* set the sign */ negate ^= 0xff; line++; } else if (*line == '+') { line++; } /* eat initial zeroes */ for (; *line == '0' && line < lineend; line++) continue; /* calculate exponents */ if (*line == DECIMAL_POINT) { /* Decimal fraction */ had_dp = 1; while (*++line == '0' && line < lineend) exponent--; } else { /* Large (absolute) value, count digits */ for (tline = line; *tline >= '0' && *tline <= '9' && tline < lineend; tline++) exponent++; } /* If the first/next character isn't a digit, value is zero */ if (*line < '1' || *line > '9' || line >= lineend) { /* This may be "0", "0.00", "000" or "fubar" but sorts as 0 */ /* XXX what about NaN, NAN, inf and INF */ *pos++ = 0x80; return pos; } /* Maybe here we should allow for e+12 (etc) */ if (exponent < 0x40 - MAX_EXP_ENC && -exponent < 0x40 - MAX_EXP_ENC) { /* Value ok for simple encoding */ /* exponent 0 is 0xc0 for +ve numbers and 0x40 for -ve ones */ exponent += 0xc0; *pos++ = negate ^ exponent; } else { /* Out or range for a single byte */ int c, t; t = exponent > 0 ? exponent : -exponent; /* Count how many 8-bit bytes are needed */ for (c = 0; ; c++) { t >>= 8; if (t == 0) break; } /* 'c' better be 0..3 here - but probably 0..1 */ /* Offset just outside valid range */ t = c + 0x40 - MAX_EXP_ENC; if (exponent < 0) t = -t; *pos++ = negate ^ (t + 0xc0); /* now add each byte, most significant first */ for (; c >= 0; c--) *pos++ = negate ^ (exponent >> (c * 8)); } /* Finally add mantissa, 2 digits per byte */ for (last_nz_pos = pos; line < lineend; ) { if (pos >= bufend) return NULL; ch = *line++; val = (ch - '0') * 10; if (val > 90) { if (ch == DECIMAL_POINT && !had_dp) { had_dp = 1; continue; } break; } while (line < lineend) { ch = *line++; if (ch == DECIMAL_POINT && !had_dp) { had_dp = 1; continue; } if (ch < '0' || ch > '9') line = lineend; else val += ch - '0'; break; } *pos++ = negate ^ (val + 0x40); if (val != 0) last_nz_pos = pos; } /* Add key terminator, deleting any trailing "00" */ *last_nz_pos++ = negate; return (last_nz_pos); } static u_char * length(u_char *pos, const u_char *bufend, u_char *line, u_char *lineend, int flag) { u_char buf[32]; int l; SKIP_BLANKS(line); l = snprintf((char *)buf, sizeof(buf), "%td", lineend - line); return number(pos, bufend, buf, buf + l, flag); }
