1/* Internal header for proving correct grouping in strings of numbers.
2   Copyright (C) 1995, 1996, 1997, 1998, 2000 Free Software Foundation, Inc.
3   This file is part of the GNU C Library.
4   Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
5
6   The GNU C Library is free software; you can redistribute it and/or
7   modify it under the terms of the GNU Lesser General Public
8   License as published by the Free Software Foundation; either
9   version 2.1 of the License, or (at your option) any later version.
10
11   The GNU C Library is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   Lesser General Public License for more details.
15
16   You should have received a copy of the GNU Lesser General Public
17   License along with the GNU C Library; if not, write to the Free
18   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19   02111-1307 USA.  */
20
21#include <limits.h>
22
23#ifndef MAX
24#define MAX(a,b)	({ typeof(a) _a = (a); typeof(b) _b = (b); \
25			   _a > _b ? _a : _b; })
26#endif
27
28/* Find the maximum prefix of the string between BEGIN and END which
29   satisfies the grouping rules.  It is assumed that at least one digit
30   follows BEGIN directly.  */
31
32static inline const STRING_TYPE *
33correctly_grouped_prefix (const STRING_TYPE *begin, const STRING_TYPE *end,
34#ifdef USE_WIDE_CHAR
35			  wchar_t thousands,
36#else
37			  const char *thousands,
38#endif
39			  const char *grouping)
40{
41#ifndef USE_WIDE_CHAR
42  size_t thousands_len;
43  int cnt;
44#endif
45
46  if (grouping == NULL)
47    return end;
48
49#ifndef USE_WIDE_CHAR
50  thousands_len = strlen (thousands);
51#endif
52
53  while (end > begin)
54    {
55      const STRING_TYPE *cp = end - 1;
56      const char *gp = grouping;
57
58      /* Check first group.  */
59      while (cp >= begin)
60	{
61#ifdef USE_WIDE_CHAR
62	  if (*cp == thousands)
63	    break;
64#else
65	  if (cp[thousands_len - 1] == *thousands)
66	    {
67	      for (cnt = 1; thousands[cnt] != '\0'; ++cnt)
68		if (thousands[cnt] != cp[thousands_len - 1 - cnt])
69		  break;
70	      if (thousands[cnt] == '\0')
71		break;
72	    }
73#endif
74	  --cp;
75	}
76
77      /* We allow the representation to contain no grouping at all even if
78	 the locale specifies we can have grouping.  */
79      if (cp < begin)
80	return end;
81
82      if (end - cp == (int) *gp + 1)
83	{
84	  /* This group matches the specification.  */
85
86	  const STRING_TYPE *new_end;
87
88	  if (cp < begin)
89	    /* There is just one complete group.  We are done.  */
90	    return end;
91
92	  /* CP points to a thousands separator character.  The preceding
93	     remainder of the string from BEGIN to NEW_END is the part we
94	     will consider if there is a grouping error in this trailing
95	     portion from CP to END.  */
96	  new_end = cp - 1;
97
98	  /* Loop while the grouping is correct.  */
99	  while (1)
100	    {
101	      /* Get the next grouping rule.  */
102	      ++gp;
103	      if (*gp == 0)
104		/* If end is reached use last rule.  */
105	        --gp;
106
107	      /* Skip the thousands separator.  */
108	      --cp;
109
110	      if (*gp == CHAR_MAX
111#if CHAR_MIN < 0
112		  || *gp < 0
113#endif
114		  )
115	        {
116	          /* No more thousands separators are allowed to follow.  */
117	          while (cp >= begin)
118		    {
119#ifdef USE_WIDE_CHAR
120		      if (*cp == thousands)
121			break;
122#else
123		      for (cnt = 0; thousands[cnt] != '\0'; ++cnt)
124			if (thousands[cnt] != cp[thousands_len - cnt - 1])
125			  break;
126		      if (thousands[cnt] == '\0')
127			break;
128#endif
129		      --cp;
130		    }
131
132	          if (cp < begin)
133		    /* OK, only digits followed.  */
134		    return end;
135	        }
136	      else
137	        {
138		  /* Check the next group.  */
139	          const STRING_TYPE *group_end = cp;
140
141		  while (cp >= begin)
142		    {
143#ifdef USE_WIDE_CHAR
144		      if (*cp == thousands)
145			break;
146#else
147		      for (cnt = 0; thousands[cnt] != '\0'; ++cnt)
148			if (thousands[cnt] != cp[thousands_len - cnt - 1])
149			  break;
150		      if (thousands[cnt] == '\0')
151			break;
152#endif
153		      --cp;
154		    }
155
156		  if (cp < begin && group_end - cp <= (int) *gp)
157		    /* Final group is correct.  */
158		    return end;
159
160		  if (cp < begin || group_end - cp != (int) *gp)
161		    /* Incorrect group.  Punt.  */
162		    break;
163		}
164	    }
165
166	  /* The trailing portion of the string starting at NEW_END
167	     contains a grouping error.  So we will look for a correctly
168	     grouped number in the preceding portion instead.  */
169	  end = new_end;
170	}
171      else
172	{
173	  /* Even the first group was wrong; determine maximum shift.  */
174	  if (end - cp > (int) *gp + 1)
175	    end = cp + (int) *gp + 1;
176	  else if (cp < begin)
177	    /* This number does not fill the first group, but is correct.  */
178	    return end;
179	  else
180	    /* CP points to a thousands separator character.  */
181	    end = cp;
182	}
183    }
184
185  return MAX (begin, end);
186}
187