diff options
| author | Lorenz Kästle <12514511+RincewindsHat@users.noreply.github.com> | 2026-03-26 12:53:53 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2026-03-26 12:53:53 +0100 |
| commit | 13e14a6bfd9f29cbfeab0c5161d2a994f97532e7 (patch) | |
| tree | 3aa7186fe092e42783dc7e981dc39a74ea61c466 /gl/memchr.c | |
| parent | 9d8503f90ef25b2cecd324dc118e441f40233ea8 (diff) | |
| download | monitoring-plugins-13e14a6bfd9f29cbfeab0c5161d2a994f97532e7.tar.gz | |
* Sync with the 202601-stable Gnulib code (4a3650d887)
* Ignore more deps stuff in gnulib
* Remove autogenerated gnulib files
* Ignore more gnulib generated headers
Diffstat (limited to 'gl/memchr.c')
| -rw-r--r-- | gl/memchr.c | 174 |
1 files changed, 86 insertions, 88 deletions
diff --git a/gl/memchr.c b/gl/memchr.c index ef0d15f7..6adac7e1 100644 --- a/gl/memchr.c +++ b/gl/memchr.c | |||
| @@ -1,4 +1,4 @@ | |||
| 1 | /* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2025 | 1 | /* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2026 |
| 2 | Free Software Foundation, Inc. | 2 | Free Software Foundation, Inc. |
| 3 | 3 | ||
| 4 | Based on strlen implementation by Torbjorn Granlund (tege@sics.se), | 4 | Based on strlen implementation by Torbjorn Granlund (tege@sics.se), |
| @@ -65,105 +65,103 @@ __memchr (void const *s, int c_in, size_t n) | |||
| 65 | performance. */ | 65 | performance. */ |
| 66 | typedef unsigned long int longword; | 66 | typedef unsigned long int longword; |
| 67 | 67 | ||
| 68 | const unsigned char *char_ptr; | 68 | unsigned reg_char c = (unsigned char) c_in; |
| 69 | const longword *longword_ptr; | ||
| 70 | longword repeated_one; | ||
| 71 | longword repeated_c; | ||
| 72 | unsigned reg_char c; | ||
| 73 | 69 | ||
| 74 | c = (unsigned char) c_in; | 70 | const longword *longword_ptr; |
| 75 | 71 | ||
| 76 | /* Handle the first few bytes by reading one byte at a time. | 72 | /* Handle the first few bytes by reading one byte at a time. |
| 77 | Do this until CHAR_PTR is aligned on a longword boundary. */ | 73 | Do this until CHAR_PTR is aligned on a longword boundary. */ |
| 78 | for (char_ptr = (const unsigned char *) s; | 74 | { |
| 79 | n > 0 && (size_t) char_ptr % sizeof (longword) != 0; | 75 | const unsigned char *char_ptr; |
| 80 | --n, ++char_ptr) | 76 | for (char_ptr = (const unsigned char *) s; |
| 81 | if (*char_ptr == c) | 77 | n > 0 && (size_t) char_ptr % sizeof (longword) != 0; |
| 82 | return (void *) char_ptr; | 78 | --n, ++char_ptr) |
| 79 | if (*char_ptr == c) | ||
| 80 | return (void *) char_ptr; | ||
| 83 | 81 | ||
| 84 | longword_ptr = (const longword *) char_ptr; | 82 | longword_ptr = (const longword *) char_ptr; |
| 83 | } | ||
| 85 | 84 | ||
| 86 | /* All these elucidatory comments refer to 4-byte longwords, | 85 | /* All these elucidatory comments refer to 4-byte longwords, |
| 87 | but the theory applies equally well to any size longwords. */ | 86 | but the theory applies equally well to any size longwords. */ |
| 88 | 87 | { | |
| 89 | /* Compute auxiliary longword values: | 88 | /* Compute auxiliary longword values: |
| 90 | repeated_one is a value which has a 1 in every byte. | 89 | repeated_one is a value which has a 1 in every byte. |
| 91 | repeated_c has c in every byte. */ | 90 | repeated_c has c in every byte. */ |
| 92 | repeated_one = 0x01010101; | 91 | longword repeated_one = 0x01010101; |
| 93 | repeated_c = c | (c << 8); | 92 | longword repeated_c = c | (c << 8); |
| 94 | repeated_c |= repeated_c << 16; | 93 | repeated_c |= repeated_c << 16; |
| 95 | if (0xffffffffU < (longword) -1) | 94 | if (0xffffffffU < (longword) -1) |
| 96 | { | 95 | { |
| 97 | repeated_one |= repeated_one << 31 << 1; | 96 | repeated_one |= repeated_one << 31 << 1; |
| 98 | repeated_c |= repeated_c << 31 << 1; | 97 | repeated_c |= repeated_c << 31 << 1; |
| 99 | if (8 < sizeof (longword)) | 98 | if (8 < sizeof (longword)) |
| 100 | { | 99 | for (size_t i = 64; i < sizeof (longword) * 8; i *= 2) |
| 101 | size_t i; | ||
| 102 | |||
| 103 | for (i = 64; i < sizeof (longword) * 8; i *= 2) | ||
| 104 | { | 100 | { |
| 105 | repeated_one |= repeated_one << i; | 101 | repeated_one |= repeated_one << i; |
| 106 | repeated_c |= repeated_c << i; | 102 | repeated_c |= repeated_c << i; |
| 107 | } | 103 | } |
| 108 | } | 104 | } |
| 109 | } | 105 | |
| 110 | 106 | /* Instead of the traditional loop which tests each byte, we will test a | |
| 111 | /* Instead of the traditional loop which tests each byte, we will test a | 107 | longword at a time. The tricky part is testing if *any of the four* |
| 112 | longword at a time. The tricky part is testing if *any of the four* | 108 | bytes in the longword in question are equal to c. We first use an xor |
| 113 | bytes in the longword in question are equal to c. We first use an xor | 109 | with repeated_c. This reduces the task to testing whether *any of the |
| 114 | with repeated_c. This reduces the task to testing whether *any of the | 110 | four* bytes in longword1 is zero. |
| 115 | four* bytes in longword1 is zero. | 111 | |
| 116 | 112 | We compute tmp = | |
| 117 | We compute tmp = | 113 | ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). |
| 118 | ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). | 114 | That is, we perform the following operations: |
| 119 | That is, we perform the following operations: | 115 | 1. Subtract repeated_one. |
| 120 | 1. Subtract repeated_one. | 116 | 2. & ~longword1. |
| 121 | 2. & ~longword1. | 117 | 3. & a mask consisting of 0x80 in every byte. |
| 122 | 3. & a mask consisting of 0x80 in every byte. | 118 | Consider what happens in each byte: |
| 123 | Consider what happens in each byte: | 119 | - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, |
| 124 | - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, | 120 | and step 3 transforms it into 0x80. A carry can also be propagated |
| 125 | and step 3 transforms it into 0x80. A carry can also be propagated | 121 | to more significant bytes. |
| 126 | to more significant bytes. | 122 | - If a byte of longword1 is nonzero, let its lowest 1 bit be at |
| 127 | - If a byte of longword1 is nonzero, let its lowest 1 bit be at | 123 | position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, |
| 128 | position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, | 124 | the byte ends in a single bit of value 0 and k bits of value 1. |
| 129 | the byte ends in a single bit of value 0 and k bits of value 1. | 125 | After step 2, the result is just k bits of value 1: 2^k - 1. After |
| 130 | After step 2, the result is just k bits of value 1: 2^k - 1. After | 126 | step 3, the result is 0. And no carry is produced. |
| 131 | step 3, the result is 0. And no carry is produced. | 127 | So, if longword1 has only non-zero bytes, tmp is zero. |
| 132 | So, if longword1 has only non-zero bytes, tmp is zero. | 128 | Whereas if longword1 has a zero byte, call j the position of the least |
| 133 | Whereas if longword1 has a zero byte, call j the position of the least | 129 | significant zero byte. Then the result has a zero at positions 0, ..., |
| 134 | significant zero byte. Then the result has a zero at positions 0, ..., | 130 | j-1 and a 0x80 at position j. We cannot predict the result at the more |
| 135 | j-1 and a 0x80 at position j. We cannot predict the result at the more | 131 | significant bytes (positions j+1..3), but it does not matter since we |
| 136 | significant bytes (positions j+1..3), but it does not matter since we | 132 | already have a non-zero bit at position 8*j+7. |
| 137 | already have a non-zero bit at position 8*j+7. | 133 | |
| 138 | 134 | So, the test whether any byte in longword1 is zero is equivalent to | |
| 139 | So, the test whether any byte in longword1 is zero is equivalent to | 135 | testing whether tmp is nonzero. */ |
| 140 | testing whether tmp is nonzero. */ | 136 | |
| 141 | 137 | while (n >= sizeof (longword)) | |
| 142 | while (n >= sizeof (longword)) | 138 | { |
| 143 | { | 139 | longword longword1 = *longword_ptr ^ repeated_c; |
| 144 | longword longword1 = *longword_ptr ^ repeated_c; | 140 | |
| 145 | 141 | if ((((longword1 - repeated_one) & ~longword1) | |
| 146 | if ((((longword1 - repeated_one) & ~longword1) | 142 | & (repeated_one << 7)) != 0) |
| 147 | & (repeated_one << 7)) != 0) | 143 | break; |
| 148 | break; | 144 | longword_ptr++; |
| 149 | longword_ptr++; | 145 | n -= sizeof (longword); |
| 150 | n -= sizeof (longword); | 146 | } |
| 151 | } | 147 | } |
| 152 | 148 | ||
| 153 | char_ptr = (const unsigned char *) longword_ptr; | 149 | { |
| 154 | 150 | const unsigned char *char_ptr = (const unsigned char *) longword_ptr; | |
| 155 | /* At this point, we know that either n < sizeof (longword), or one of the | 151 | |
| 156 | sizeof (longword) bytes starting at char_ptr is == c. On little-endian | 152 | /* At this point, we know that either n < sizeof (longword), or one of the |
| 157 | machines, we could determine the first such byte without any further | 153 | sizeof (longword) bytes starting at char_ptr is == c. On little-endian |
| 158 | memory accesses, just by looking at the tmp result from the last loop | 154 | machines, we could determine the first such byte without any further |
| 159 | iteration. But this does not work on big-endian machines. Choose code | 155 | memory accesses, just by looking at the tmp result from the last loop |
| 160 | that works in both cases. */ | 156 | iteration. But this does not work on big-endian machines. Choose code |
| 161 | 157 | that works in both cases. */ | |
| 162 | for (; n > 0; --n, ++char_ptr) | 158 | |
| 163 | { | 159 | for (; n > 0; --n, ++char_ptr) |
| 164 | if (*char_ptr == c) | 160 | { |
| 165 | return (void *) char_ptr; | 161 | if (*char_ptr == c) |
| 166 | } | 162 | return (void *) char_ptr; |
| 163 | } | ||
| 164 | } | ||
| 167 | 165 | ||
| 168 | return NULL; | 166 | return NULL; |
| 169 | } | 167 | } |
