blob: 236b970dd2dbb6e87bb7feb1ff0da885822018b5 [file] [log] [blame]
Willy Tarreau214c2032009-02-20 11:02:32 +01001/*
2 * fast fgets() replacement for log parsing
3 *
4 * Copyright 2000-2009 Willy Tarreau <w@1wt.eu>
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 *
11 * This function manages its own buffer and returns a pointer to that buffer
12 * in order to avoid expensive memory copies. It also checks for line breaks
13 * 32 bits at a time. It could be improved a lot using mmap() but we would
14 * not be allowed to replace trailing \n with zeroes and we would be limited
15 * to small log files on 32-bit machines.
16 *
17 */
18
19#include <stdlib.h>
20#include <string.h>
21#include <stdio.h>
22#include <unistd.h>
23
24// return 1 if the integer contains at least one zero byte
25static inline unsigned int has_zero(unsigned int x)
26{
Willy Tarreau1769a182010-05-04 10:47:57 +020027 unsigned int y;
28
29 /* Principle: we want to perform 4 tests on one 32-bit int at once. For
30 * this, we have to simulate an SIMD instruction which we don't have by
31 * default. The principle is that a zero byte is the only one which
32 * will cause a 1 to appear on the upper bit of a byte/word/etc... when
33 * we subtract 1. So we can detect a zero byte if a one appears at any
34 * of the bits 7, 15, 23 or 31 where it was not. It takes only one
35 * instruction to test for the presence of any of these bits, but it is
36 * still complex to check for their initial absence. Thus, we'll
37 * proceed differently : we first save and clear only those bits, then
38 * we check in the final result if one of them is present and was not.
39 */
40 y = x;
41 x = ~x & 0x80808080; /* save and invert bits 7, 15, 23, 31 */
42 y &= 0x7F7F7F7F; /* clear them */
43 y -= 0x01010101; /* generate a carry */
44 y &= x; /* clear the bits that were already set */
45 return !!y;
Willy Tarreau214c2032009-02-20 11:02:32 +010046}
47
Willy Tarreau1769a182010-05-04 10:47:57 +020048
49// return 1 if the argument contains at least one zero byte. See principle above.
Willy Tarreau214c2032009-02-20 11:02:32 +010050static inline unsigned int has_zero64(unsigned long long x)
51{
Willy Tarreau1769a182010-05-04 10:47:57 +020052 unsigned long long y;
Willy Tarreau214c2032009-02-20 11:02:32 +010053
Willy Tarreau1769a182010-05-04 10:47:57 +020054 y = x;
55 x = ~x & 0x8080808080808080ULL; /* save bits 7, 15, 23, 31, 39, 47, 55 and 63 */
56 y &= 0x7F7F7F7F7F7F7F7FULL; /* clear them */
57 y -= 0x0101010101010101ULL; /* generate a carry */
58 y &= x; /* clear the bits that were already set */
59 return !!y;
Willy Tarreau214c2032009-02-20 11:02:32 +010060}
61
62#define FGETS2_BUFSIZE (256*1024)
63const char *fgets2(FILE *stream)
64{
Willy Tarreaud2c142c2010-05-05 12:22:08 +020065 static char buffer[FGETS2_BUFSIZE + 9]; // +9 to have zeroes past the end
Willy Tarreau214c2032009-02-20 11:02:32 +010066 static char *end = buffer;
67 static char *line = buffer;
68
69 char *next;
70 int ret;
71
72 next = line;
73
74 while (1) {
Willy Tarreaud2c142c2010-05-05 12:22:08 +020075 /* this is a speed-up, we read 64 bits at once and check for an
Willy Tarreau214c2032009-02-20 11:02:32 +010076 * LF character there. We stop if found then continue one at a
77 * time.
78 */
Willy Tarreau214c2032009-02-20 11:02:32 +010079
Willy Tarreaud2c142c2010-05-05 12:22:08 +020080 if (next <= (end-12)) {
81 /* max 3 bytes tested here */
82 while ((((unsigned long)next) & 3) && *next != '\n')
83 next++;
84
85 /* maybe we have can skip 4 more bytes */
86 if ((((unsigned long)next) & 4) && !has_zero(*(unsigned int *)next ^ 0x0A0A0A0AU))
87 next += 4;
88 }
89
90 /* now next is multiple of 8 or equal to end */
91 while (next <= (end-68)) {
92 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
93 break;
94 next += 8;
95 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
96 break;
97 next += 8;
98 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
99 break;
100 next += 8;
Willy Tarreau214c2032009-02-20 11:02:32 +0100101 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
102 break;
103 next += 8;
104 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
105 break;
106 next += 8;
107 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
108 break;
109 next += 8;
110 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
111 break;
112 next += 8;
Willy Tarreaud2c142c2010-05-05 12:22:08 +0200113 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
114 break;
115 next += 8;
Willy Tarreau214c2032009-02-20 11:02:32 +0100116 }
117
Willy Tarreaud2c142c2010-05-05 12:22:08 +0200118 /* maybe we can skip 4 more bytes */
119 if (!has_zero(*(unsigned int *)next ^ 0x0A0A0A0AU))
120 next += 4;
121
Willy Tarreau214c2032009-02-20 11:02:32 +0100122 /* we finish if needed. Note that next might be slightly higher
123 * than end here because we might have gone past it above.
124 */
125 while (next < end) {
126 if (*next == '\n') {
127 const char *start = line;
128
129 *next = '\0';
130 line = next + 1;
131 return start;
132 }
133 next++;
134 }
135
136 /* we found an incomplete line. First, let's move the
137 * remaining part of the buffer to the beginning, then
138 * try to complete the buffer with a new read.
139 */
140 if (line > buffer) {
141 if (end != line)
142 memmove(buffer, line, end - line);
143 end = buffer + (end - line);
144 next = end;
145 line = buffer;
146 } else {
147 if (end == buffer + FGETS2_BUFSIZE)
148 return NULL;
149 }
150
151 ret = read(fileno(stream), end, buffer + FGETS2_BUFSIZE - end);
152
153 if (ret <= 0) {
154 if (end == line)
155 return NULL;
156
157 *end = '\0';
158 return line;
159 }
160
161 end += ret;
162 /* search for '\n' again */
163 }
164}
165
166#ifdef BENCHMARK
167int main() {
168 const char *p;
169 unsigned int lines = 0;
170
171 while ((p=fgets2(stdin)))
172 lines++;
173 printf("lines=%d\n", lines);
174 return 0;
175}
176#endif