1 /* Compare numeric strings.  This is an internal include file.
2 
3    Copyright (C) 1988-2023 Free Software Foundation, Inc.
4 
5    This program is free software: you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation, either version 3 of the License, or
8    (at your option) any later version.
9 
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14 
15    You should have received a copy of the GNU General Public License
16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
17 
18 /* Written by Mike Haertel.  */
19 
20 #ifndef STRNUMCMP_IN_H
21 # define STRNUMCMP_IN_H 1
22 
23 # include "strnumcmp.h"
24 
25 # include <stddef.h>
26 
27 # define NEGATION_SIGN   '-'
28 # define NUMERIC_ZERO    '0'
29 
30 /* ISDIGIT differs from isdigit, as follows:
31    - Its arg may be any int or unsigned int; it need not be an unsigned char
32      or EOF.
33    - It's typically faster.
34    POSIX says that only '0' through '9' are digits.  Prefer ISDIGIT to
35    isdigit unless it's important to use the locale's definition
36    of 'digit' even when the host does not conform to POSIX.  */
37 # define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9)
38 
39 
40 /* Compare strings A and B containing decimal fractions < 1.
41    DECIMAL_POINT is the decimal point.  Each string
42    should begin with a decimal point followed immediately by the digits
43    of the fraction.  Strings not of this form are treated as zero.  */
44 
45 /* The goal here, is to take two numbers a and b... compare these
46    in parallel.  Instead of converting each, and then comparing the
47    outcome.  Most likely stopping the comparison before the conversion
48    is complete.  The algorithm used, in the old "sort" utility:
49 
50    Algorithm: fraccompare
51    Action   : compare two decimal fractions
52    accepts  : char *a, char *b
53    returns  : -1 if a<b, 0 if a=b, 1 if a>b.
54    implement:
55 
56    if *a == decimal_point AND *b == decimal_point
57      find first character different in a and b.
58      if both are digits, return the difference *a - *b.
59      if *a is a digit
60        skip past zeros
61        if digit return 1, else 0
62      if *b is a digit
63        skip past zeros
64        if digit return -1, else 0
65    if *a is a decimal_point
66      skip past decimal_point and zeros
67      if digit return 1, else 0
68    if *b is a decimal_point
69      skip past decimal_point and zeros
70      if digit return -1, else 0
71    return 0 */
72 
73 static inline int _GL_ATTRIBUTE_PURE
fraccompare(char const * a,char const * b,char decimal_point)74 fraccompare (char const *a, char const *b, char decimal_point)
75 {
76   if (*a == decimal_point && *b == decimal_point)
77     {
78       while (*++a == *++b)
79         if (! ISDIGIT (*a))
80           return 0;
81       if (ISDIGIT (*a) && ISDIGIT (*b))
82         return *a - *b;
83       if (ISDIGIT (*a))
84         goto a_trailing_nonzero;
85       if (ISDIGIT (*b))
86         goto b_trailing_nonzero;
87       return 0;
88     }
89   else if (*a++ == decimal_point)
90     {
91     a_trailing_nonzero:
92       while (*a == NUMERIC_ZERO)
93         a++;
94       return ISDIGIT (*a);
95     }
96   else if (*b++ == decimal_point)
97     {
98     b_trailing_nonzero:
99       while (*b == NUMERIC_ZERO)
100         b++;
101       return - ISDIGIT (*b);
102     }
103   return 0;
104 }
105 
106 /* Compare strings A and B as numbers without explicitly converting
107    them to machine numbers, to avoid overflow problems and perhaps
108    improve performance.  DECIMAL_POINT is the decimal point and
109    THOUSANDS_SEP the thousands separator.  A DECIMAL_POINT outside
110    'char' range causes comparisons to act as if there is no decimal point
111    character, and likewise for THOUSANDS_SEP.  */
112 
113 static inline int _GL_ATTRIBUTE_PURE
numcompare(char const * a,char const * b,int decimal_point,int thousands_sep)114 numcompare (char const *a, char const *b,
115             int decimal_point, int thousands_sep)
116 {
117   unsigned char tmpa = *a;
118   unsigned char tmpb = *b;
119   int tmp;
120   size_t log_a;
121   size_t log_b;
122 
123   if (tmpa == NEGATION_SIGN)
124     {
125       do
126         tmpa = *++a;
127       while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep);
128       if (tmpb != NEGATION_SIGN)
129         {
130           if (tmpa == decimal_point)
131             do
132               tmpa = *++a;
133             while (tmpa == NUMERIC_ZERO);
134           if (ISDIGIT (tmpa))
135             return -1;
136           while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep)
137             tmpb = *++b;
138           if (tmpb == decimal_point)
139             do
140               tmpb = *++b;
141             while (tmpb == NUMERIC_ZERO);
142           return - ISDIGIT (tmpb);
143         }
144       do
145         tmpb = *++b;
146       while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep);
147 
148       while (tmpa == tmpb && ISDIGIT (tmpa))
149         {
150           do
151             tmpa = *++a;
152           while (tmpa == thousands_sep);
153           do
154             tmpb = *++b;
155           while (tmpb == thousands_sep);
156         }
157 
158       if ((tmpa == decimal_point && !ISDIGIT (tmpb))
159           || (tmpb == decimal_point && !ISDIGIT (tmpa)))
160         return fraccompare (b, a, decimal_point);
161 
162       tmp = tmpb - tmpa;
163 
164       for (log_a = 0; ISDIGIT (tmpa); ++log_a)
165         do
166           tmpa = *++a;
167         while (tmpa == thousands_sep);
168 
169       for (log_b = 0; ISDIGIT (tmpb); ++log_b)
170         do
171           tmpb = *++b;
172         while (tmpb == thousands_sep);
173 
174       if (log_a != log_b)
175         return log_a < log_b ? 1 : -1;
176 
177       if (!log_a)
178         return 0;
179 
180       return tmp;
181     }
182   else if (tmpb == NEGATION_SIGN)
183     {
184       do
185         tmpb = *++b;
186       while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep);
187       if (tmpb == decimal_point)
188         do
189           tmpb = *++b;
190         while (tmpb == NUMERIC_ZERO);
191       if (ISDIGIT (tmpb))
192         return 1;
193       while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep)
194         tmpa = *++a;
195       if (tmpa == decimal_point)
196         do
197           tmpa = *++a;
198         while (tmpa == NUMERIC_ZERO);
199       return ISDIGIT (tmpa);
200     }
201   else
202     {
203       while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep)
204         tmpa = *++a;
205       while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep)
206         tmpb = *++b;
207 
208       while (tmpa == tmpb && ISDIGIT (tmpa))
209         {
210           do
211             tmpa = *++a;
212           while (tmpa == thousands_sep);
213           do
214             tmpb = *++b;
215           while (tmpb == thousands_sep);
216         }
217 
218       if ((tmpa == decimal_point && !ISDIGIT (tmpb))
219           || (tmpb == decimal_point && !ISDIGIT (tmpa)))
220         return fraccompare (a, b, decimal_point);
221 
222       tmp = tmpa - tmpb;
223 
224       for (log_a = 0; ISDIGIT (tmpa); ++log_a)
225         do
226           tmpa = *++a;
227         while (tmpa == thousands_sep);
228 
229       for (log_b = 0; ISDIGIT (tmpb); ++log_b)
230         do
231           tmpb = *++b;
232         while (tmpb == thousands_sep);
233 
234       if (log_a != log_b)
235         return log_a < log_b ? -1 : 1;
236 
237       if (!log_a)
238         return 0;
239 
240       return tmp;
241     }
242 }
243 
244 #endif
245