3479
2006-11-07 17:20:25 +0000
Incorrect rounding in strtod()
2016-05-08 14:10:58 +0000
1
1
1
Unclassified
glibc
libc
unspecified
All
All
RESOLVED
FIXED
P2
normal
---
1
hack
jsm28
bugdal
exploringbinary
floitsch
glibc-bugs
john
mwelinder
Sylvain.Pion
vincent-srcware
oldest_to_newest
13179
0
hack
2006-11-07 17:20:25 +0000
There is a subtle rounding error in decimal_string->BFP conversion
(e.g. strtod()) for values that are equal to, or very close to,
half-way points, i.e. sufficiently-long prefixes of the exact decimal
representation of a binary half-way point.
An example is strtod(" 3.518437208883201171875E+013 ") which truncates
to the odd 0x42c0000000000001 when in fact default IEEE rounding should
have rounded up to 0x42c0000000000002 (nearest-ties-to-even).
In fact, strtod only looks at the first 20 digits (well, it scans the
others for validity), so that strtod(" 3.518437208883201171999E+013 "
also rounds down, even though it is definitely above the half-way point.
Indeed, with an extended fraction this would be
JL16'+3.518437208883201171999E+013' = 42C00000 00000001 800A66E1 358F83EC
(This is the output of the IBM Research experimental assembler Phantasm,
for which I wrote the conversion routines ten years ago.)
The first number to round up correctly is "3.518437208883201172000E+013".
* (I hope a fixed-width font is used here) ....:....1....:....2....:....3
Here is the broken part of strtod.c -- the comment is simply wrong in
the case of exact half-way numbers, where all digits are significant
in order to determine which way to round!
/* For the fractional part we need not process too many digits. One
decimal digits gives us log_2(10) ~ 3.32 bits. If we now compute
ceil(BITS / 3) =: N
digits we should have enough bits for the result. The remaining
decimal digits give us the information that more bits are following.
This can be used while rounding. (One added as a safety margin.) */
if (dig_no - int_no > (MANT_DIG - bits + 2) / 3 + 1)
{
dig_no = int_no + (MANT_DIG - bits + 2) / 3 + 1;
more_bits = 1;
}
else
more_bits = 0;
The basic idea of limiting the number of decimal digits that need to
participate in conversion arithmetic is a good one, btw; it's just that
the limit picked by strtod() is too small and does not take the exponent
into account.
As many digits as it takes to represent a binary halfway point exactly
must be processed. The worst case is 752 digits for double, for numbers
near Nmin/2. If the binary exponent is known at this point (I think it
is, based on quick code browsing), the max can be computed. I enclose
the comments from my own conversion program:
*
* When the normalised binary exponent B exceeds the frac-
* tion length F (in bits), the length of an exact decimal
* represention is .3 B digits, otherwise (e.g. negative B)
* it is (F + .7 B) digits (or (F-B) + .3 B). We need to
* detect exact half-way points, so we need to consider F+1
* instead of the F derived from the format.
*
(Here .3 and .7 are short for log10(2) and log10(5) of course.)
Michel.
14858
1
john
2007-02-04 19:37:11 +0000
I just encountered something very similar. I started looking at C++
operator>>, which led me to scanf, which led me to strtof. It appears
that glibc's strtof doesn't adhere to the "Recommended Practice" of
section 6.4.4.2 and 7.20.1.3 of C99. I see numerous FAILs in the
attached code with strtof. I haven't seen any problems with strtod,
but I haven't done exhaustive tests. Platforms:
Opteron, Centos, glibc-2.3.4-2, gcc-4.1.1
Pentium 4, Fedora, glibc-2.3.3-27.1, gcc-3.3.3-7
I have not tested against glibc's CVS, but even if it passes, I would
suggest that something like the tests here belong in the test suite.
The recommended practice for literal floating constants in 6.4.4.2 is:
The translation-time conversion of floating constants should
match the execution-time conversion of character strings by library
functions, such as strtod, given matching inputs suitable for both
conversions, the same result format, and default execution-time
rounding.63)
63) The specification for the library functions
recommends more accurate conversion than required for floating
constants (see 7.20.1.3).
The attached code checks this condition. It's *much* easier to check
this than to check the more detailed requirement of 7.20.1.3. As a
result, the code doesn't actually prove that glibc is in error. It's
possible that gcc's handling of literal floats is in error.
The recommended practice for strto* in 7.20.1.3 is:
If the subject sequence has the decimal form and at most
DECIMAL_DIG (defined in <float.h>) significant digits, the result
should be correctly rounded. If the subject sequence D has the
decimal form and more than DECIMAL_DIG significant digits,
consider the two bounding, adjacent decimal strings L and U, both
having DECIMAL_DIG significant digits, such that the values of L,
D, and U satisfy L <= D <= U. The result should be one of the
(equal or adjacent) values that would be obtained by correctly
rounding L and U according to the current rounding direction,
with the extra stipulation that the error with respect to D
should have a correct sign for the current rounding direction.
The decimal strings in the attached test case are all less than or
equal to DECIMAL_DIG in length.
A close look at the output suggests that glibc is in error, at least
if one believes the output of printf("%.30g"). For example, for the
first FAIL:
The input string is:
"1.00000005960464477550"
The possible neighboring floats are:
"1.00000011920928955078125000000" (printf("%.30g", 1 + FLT_EPSILON))
and
"1.0"
According to dc, the distance from the input to 1+FLT_EPSILON is:
.00000005960464477528125000000
and the distance from the input to 1.0 is
.00000005960464477550
so 1+FLT_EPSILON should be the "correct" properly rounded result.
strtof returns 1.0.
---------------------------------------
[jsalmon@river lexical_cast]$ cat badstrtod2.c
#define _ISOC99_SOURCE_
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <float.h>
void checkf(const char *s, float f){
float cf = strtof(s, NULL);
long double cld = strtold(s, NULL);
if( cf != f ){
printf("FAIL strtof (\"%s\") %a is not the same as literal %a\n",
s, cf, f);
}else{
printf("OK strtof (\"%s\") %a is the same as literal\n",
s, cf);
}
}
void checkd(const char *s, double d){
double cd = strtod(s, NULL);
if( cd != d ){
printf("FAIL strtod (\"%s\") %a is not the same as literal %a\n",
s, cd, d);
}else{
printf("OK strtod (\"%s\") %a is the same as literal\n",
s, cd);
}
}
int main(int argc, char **argv){
long double ld;
/* Put some context in the output. These are not used for testing */
ld = 1.L + (long double)FLT_EPSILON;
printf("1 + FLT_EPSILON: %La %#.30Lg\n", ld, ld);
ld = 1.L + ((long double)FLT_EPSILON)/2.;
printf("1 + FLT_EPSILON/2.: %La %#.30Lg\n", ld, ld);
ld = 1.L + ((long double)FLT_EPSILON)/2. + LDBL_EPSILON;
printf("1 + FLT_EPSILON/2. + LDBL_EPSILON: %La %#.30Lg\n", ld, ld);
#define CHKF(s) checkf(#s, s##f);
/* 1 + FLT_EPSILON/2. + LDBL_EPSILON */
CHKF(1.00000005960464477550);
CHKF(1.0000000596046447755);
CHKF(1.000000059604644776);
CHKF(1.000000059604644775);
CHKF(1.00000005960464478);
CHKF(1.0000000596046448);
CHKF(1.000000059604645);
CHKF(1.00000005960464);
CHKF(1.0000000596046);
CHKF(1.000000059605);
CHKF(1.00000005960);
CHKF(1.0000000596);
CHKF(1.000000060);
CHKF(1.00000006);
CHKF(1.0000001);
CHKF(1.000000);
ld = 1.L + (long double)DBL_EPSILON;
printf("1 + DBL_EPSILON: %La %#.30Lg\n", ld, ld);
ld = 1.L + ((long double)DBL_EPSILON)/2.;
printf("1 + DBL_EPSILON/2.: %La %#.30Lg\n", ld, ld);
ld = 1.L + ((long double)DBL_EPSILON)/2. + LDBL_EPSILON;
printf("1 + DBL_EPSILON/2. + LDBL_EPSILON: %La %#.30Lg\n", ld, ld);
#define CHKD(s) checkd(#s, s);
CHKD(1.00000000000000011113);
CHKD(1.00000000000000011103);
CHKD(1.00000000000000011102);
CHKD(1.00000000000000011101);
CHKD(1.0000000000000001111);
CHKD(1.000000000000000111);
CHKD(1.00000000000000011);
CHKD(1.0000000000000001);
return 0;
}
[jsalmon@river lexical_cast]$
[jsalmon@river lexical_cast]$ gcc -g -std=c99 badstrtod2.c -lm -o badstrtod2 &&
badstrtod2
1 + FLT_EPSILON: 0x8.00001p-3 1.00000011920928955078125000000
1 + FLT_EPSILON/2.: 0x8.000008p-3 1.00000005960464477539062500000
1 + FLT_EPSILON/2. + LDBL_EPSILON: 0x8.000008000000001p-3
1.00000005960464477549904521725
FAIL strtof ("1.00000005960464477550") 0x1p+0 is not the same as literal
0x1.000002p+0
FAIL strtof ("1.0000000596046447755") 0x1p+0 is not the same as literal
0x1.000002p+0
FAIL strtof ("1.000000059604644776") 0x1p+0 is not the same as literal 0x1.000002p+0
OK strtof ("1.000000059604644775") 0x1p+0 is the same as literal
FAIL strtof ("1.00000005960464478") 0x1p+0 is not the same as literal 0x1.000002p+0
FAIL strtof ("1.0000000596046448") 0x1p+0 is not the same as literal 0x1.000002p+0
FAIL strtof ("1.000000059604645") 0x1p+0 is not the same as literal 0x1.000002p+0
OK strtof ("1.00000005960464") 0x1p+0 is the same as literal
OK strtof ("1.0000000596046") 0x1p+0 is the same as literal
FAIL strtof ("1.000000059605") 0x1p+0 is not the same as literal 0x1.000002p+0
OK strtof ("1.00000005960") 0x1p+0 is the same as literal
OK strtof ("1.0000000596") 0x1p+0 is the same as literal
OK strtof ("1.000000060") 0x1.000002p+0 is the same as literal
OK strtof ("1.00000006") 0x1.000002p+0 is the same as literal
OK strtof ("1.0000001") 0x1.000002p+0 is the same as literal
OK strtof ("1.000000") 0x1p+0 is the same as literal
1 + DBL_EPSILON: 0x8.0000000000008p-3 1.00000000000000022204460492503
1 + DBL_EPSILON/2.: 0x8.0000000000004p-3 1.00000000000000011102230246252
1 + DBL_EPSILON/2. + LDBL_EPSILON: 0x8.000000000000401p-3
1.00000000000000011113072267976
OK strtod ("1.00000000000000011113") 0x1.0000000000001p+0 is the same as literal
OK strtod ("1.00000000000000011103") 0x1.0000000000001p+0 is the same as literal
OK strtod ("1.00000000000000011102") 0x1p+0 is the same as literal
OK strtod ("1.00000000000000011101") 0x1p+0 is the same as literal
OK strtod ("1.0000000000000001111") 0x1.0000000000001p+0 is the same as literal
OK strtod ("1.000000000000000111") 0x1p+0 is the same as literal
OK strtod ("1.00000000000000011") 0x1p+0 is the same as literal
OK strtod ("1.0000000000000001") 0x1p+0 is the same as literal
[jsalmon@river lexical_cast]$
14867
2
joseph
2007-02-05 16:48:13 +0000
Subject: Re: Incorrect rounding in strtod()
On Sun, 4 Feb 2007, john at thesalmons dot org wrote:
> The attached code checks this condition. It's *much* easier to check
> this than to check the more detailed requirement of 7.20.1.3. As a
> result, the code doesn't actually prove that glibc is in error. It's
> possible that gcc's handling of literal floats is in error.
We know GCC's handling of floating-point literals doesn't always get the
last bit rounded correctly, but showing this requires specially chosen
examples (that I could only find for IEEE quad long double). So the cases
here probably don't result from a GCC bug - but it might still be wise to
write such tests so that GCC only needs parse a hex float value, so as to
disentangle the glibc and GCC issues.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21718
14869
3
hack
2007-02-05 18:31:51 +0000
There are two issues here: compile-time and run-time match, and correct rounding.
The second issue is one way to achieve the first: if both environments round
correctly all given digits, the results will match no matter how this is
implemented. A more common approach is to reuire the use of the same library
routine in both environments -- but that is difficult to guarantee as libraries
evolve, possibly in the direction of supporting more correctly-rounded digits.
Another method is to legislate some imperfect method, e.g. first round (in
decimal) to some standard number of digits, then convert that with correct
rounding to the target binary format.
It looks like gcc took the first approach (using gmp as its high-precision
engine), but has a simple bug: an invalid shortcut that fails for numbers that
are very close to a rounding threshold, as is John's example.
My program PHL converts to various precisions; K=Binary128, J=Binary64 (aka
double), and I=Binary32 (aka float); the L modifier overrides the natural length
of the format, and I use it show bits way beyond the rounding point. The number
is indeed slightly larger than a half-way float, but it takes extended precision
to see it; 10-byte Intel long double (a format that I don't support directly)
looks like it would just show one non-zero tail bit.
The input string is:
"1.00000005960464477550"
PHL K 1.00000005960464477550= * 3FFF0000 01000000 00020482 42F2FF67
PHL J 1.00000005960464477550= * 3FF00000 10000000
PHL JL16 1.00000005960464477550= * 3FF00000 10000000 00204824 2F2FF66C
PHL IL16 1.00000005960464477550= * 3F800000 80000000 01024121 797FB363
PHL IL8 1.00000005960464477550= * 3F800000 80000000
PHL I 1.00000005960464477550= * 3F800001
Btw, such numbers can be generated (for any precision) by using Continued
Fraction expansions of ratios of powers of two and five.
Michel
14876
4
john
2007-02-05 21:54:35 +0000
I was not sufficiently clear in Comment #2.
The fact that the code prints FAIL in certain cases does not demonstrate whether
gcc's literal parser or glibc's strtof is faulty. It only proves that (at
least) one of them is failing to adhere to "Recommended Practice" which says
they should be the same.
HOWEVER, careful inspection of the output, as well as knowledge of how the
particular test case was chosen makes it pretty clear that *for this case* gcc
is doing the right thing and strtof is at fault. gcc's rounding may not be
perfect, but that's not at issue here.
The input, "1.00000005960464477550" is the result of printf("%.21g", x)
where x = 1 + FLT_EPSILON/2 + LDBL_EPSILON. I.e., it is specifically
constructed to be *just a little bit larger* than the mid-point between two
representable floats. Correct rounding should be to the larger of the two
nearby floats, i.e., 1+FLT_EPSILON. gcc correctly constructs the literal
0x1.00002p0. strof incorrectly returns the value 1.0p0.
15040
5
1550
jakub
2007-02-12 17:04:18 +0000
Created attachment 1550
bz3479.c
It seems that both GCC and glibc are buggy, even on floats.
37144
6
Sylvain.Pion
2009-07-15 14:58:56 +0000
Besides the "Recommended practice" mentioned, Annex F on IEC 60559
floating-point arithmetic, also says :
"Functions such as strtod that convert character sequences to floating
types must honor the rounding direction."
It seems like glibc does not honor this, as the following program
illustrates by crashing (on x86_64-linux at least).
#include <stdlib.h>
#include <assert.h>
#include <fenv.h>
int main()
{
fesetround(FE_UPWARD);
double d = strtod("0.3", (char**) NULL);
fesetround(FE_DOWNWARD);
double e = strtod("0.3", (char**) NULL);
assert(d != e);
}
37147
7
vincent-srcware
2009-07-15 15:50:16 +0000
The fact that the rounding direction is not taken into account could be seen as
a different bug. Concerning printf, see bug 5044.
37148
8
Sylvain.Pion
2009-07-15 16:21:12 +0000
I agree, and I also wondered about this before posting my comment, but I decided
to leave this up to the bug database maintainers to eventually split it, as they
are so close and I am not familiar with the local policy.
Nevertheless, there is also a closely related point in my comment, which is that
in default rounding mode (to nearest), the Annex F says that the rounding should
be done to the nearest. And I understand that this applies to *all input*, so
it seems to me that this supersedes the "recommended practice" paragraph which
restricts the application to only some input (those with less significant digits
than DECIMAL_DIG).
43494
9
exploringbinary
2010-06-04 01:02:29 +0000
Regarding the example 3.518437208883201171875e+013, I think you can see what's
going on better by looking at its value in "pure" binary:
1000000000000000000000000000000000000000000000.00000011
It has 54 significant bits, with bit 54 equal to 1 -- a halfway case. Since bit
53 is also 1, it should round up to
1000000000000000000000000000000000000000000000.000001
I've written an article describing this and other examples of incorrectly
rounded conversions:
http://www.exploringbinary.com/incorrectly-rounded-conversions-in-gcc-and-glibc/ .
43495
10
exploringbinary
2010-06-04 01:03:32 +0000
Regarding the example 3.518437208883201171875e+013, I think you can see what's
going on better by looking at its value in "pure" binary:
1000000000000000000000000000000000000000000000.00000011
It has 54 significant bits, with bit 54 equal to 1 -- a halfway case. Since bit
53 is also 1, it should round up to
1000000000000000000000000000000000000000000000.000001
I've written an article describing this and other examples of incorrectly
rounded conversions:
http://www.exploringbinary.com/incorrectly-rounded-conversions-in-gcc-and-glibc/ .
44874
11
schwab
2010-09-02 16:24:38 +0000
*** Bug 11877 has been marked as a duplicate of this bug. ***
51704
12
mwelinder
2011-11-12 16:10:41 +0000
Is there any reason not to fix this by removing the limit on digits
considered? Or by upping it to (say) the maximum binary exponent?
54908
13
jsm28
2012-05-02 10:00:53 +0000
*** Bug 14046 has been marked as a duplicate of this bug. ***
54919
14
bugdal
2012-05-02 15:22:54 +0000
Doing this correctly in the naive way requires some expensive extended-precision arithmetic. I think one (possibly) less expensive solution can be found in John Salmon's citation of the recommended practice. If you compute the result based on DECIMAL_DIG digits in the existing manner, but do it for BOTH the neighboring values L and U. If the results for L and U are equal, you're done. If not, you have to determine which of the two D is closer to (for default rounding mode; other rounding modes are much easier) and this probably involves converting at least one of them back to decimal, which might cost you more than just doing the full-precision original calculation...
54925
15
floitsch
2012-05-02 16:00:15 +0000
The double-conversion routines extracted from v8 (Chrome's JS engine) are pretty fast and handle corner cases correctly:
http://code.google.com/p/double-conversion
It would probably require some engineering effort to translate the code from C++ to C and to adapt it to all of libc's requirements (for example the library always rounds to even), but it might serve as a decent starting-point.
Another hurdle might be the requirement for a cache of precomputed 64bit values. However, some size could probably be traded against speed.
54928
16
joseph
2012-05-02 16:52:57 +0000
I expect that simply using the existing GMP-based code but with a correct
calculation of how many digits need considering would suffice to fix the
present problem. Rounding according to the current rounding mode is a
separate issue that really ought to have its own bug.
56835
17
jsm28
2012-08-10 23:40:28 +0000
Working on a patch (for the bad results for round-to-nearest, that is; not the lack of rounding mode support in strtod etc. which should have a separate bug filed).
57120
18
jsm28
2012-08-25 15:27:40 +0000
I've filed bug 14518 for the issue (comment 6) with non-default rounding modes being ignored.
57121
19
floitsch
2012-08-25 15:29:20 +0000
I'm on vacation, returning August 29.
57141
20
jsm28
2012-08-27 16:12:54 +0000
Fixed for 2.17 by:
commit af92131a8eb7c2661a5bb0e31dc4cb028c85e0c6
Author: Joseph Myers <joseph@codesourcery.com>
Date: Mon Aug 27 16:01:27 2012 +0000
Fix strtod rounding (bug 3479).
64428
21
exploringbinary
2013-11-12 16:43:47 +0000
The fix tests well (http://www.exploringbinary.com/correctly-rounded-conversions-in-gcc-and-glibc/ ), but has one very minor bug (http://sourceware.org/bugzilla/show_bug.cgi?id=16151 ).
66592
22
jackie.rosen
2014-02-16 16:56:59 +0000
*** Bug 260998 has been marked as a duplicate of this bug. ***
Seen from the domain http://volichat.com
Page where seen: http://volichat.com/adult-chat-rooms
Marked for reference. Resolved as fixed @bugzilla.
1550
2007-02-12 17:04:18 +0000
2007-02-12 17:04:18 +0000
bz3479.c
bz3479.c
text/plain
1285
jakub
I2RlZmluZSBfWE9QRU5fU09VUkNFIDEKI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRs
aWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKc3RhdGljIGNvbnN0IHN0cnVjdAp7CiAgY29uc3Qg
Y2hhciAqc3RyOwogIGxvbmcgZG91YmxlIGM7CiAgbG9uZyBkb3VibGUgZXhwZWN0ZWQ7CiAgaW50
IHR5cGU7Cn0gdGVzdHNbXSA9CnsKI2RlZmluZSBGKHYsIGV4cGVjdGVkKSBcCiAgeyAjdiwgdiMj
ZiwgZXhwZWN0ZWQsICdmJyB9CiNkZWZpbmUgRCh2LCBleHBlY3RlZCkgXAogIHsgI3YsIHYsIGV4
cGVjdGVkLCAnZCcgfQojZGVmaW5lIEwodiwgZXhwZWN0ZWQpIFwKICB7ICN2LCB2IyNMLCBleHBl
Y3RlZCwgJ2wnIH0KICAvKiAxLjAgKi8KICBGICgxLjAsIDEuMEwpLAogIEYgKDEuMDAwMDAwMDU5
NjA0NjQ0Nzc1MzkwNjI0OTksIDEuMEwpLAogIC8qIDEuMCArIEZMVF9FUFNJTE9OIC8gMiAqLwog
IEYgKDEuMDAwMDAwMDU5NjA0NjQ0Nzc1MzkwNjI1LCAxLjBMKSwKICBGICgxLjAwMDAwMDA1OTYw
NDY0NDc3NTM5MDYyNTAxLCAweDEuMDAwMDAycCswTCksCiAgLyogMS4wICsgRkxUX0VQU0lMT04g
Ki8KICBGICgxLjAwMDAwMDExOTIwOTI4OTU1MDc4MTI1LCAweDEuMDAwMDAycCswTCksCiAgRiAo
MS4wMDAwMDAxNzg4MTM5MzQzMjYxNzE4NzQ5OSwgMHgxLjAwMDAwMnArMEwpLAogIC8qIDEuMCAr
IDMgKiBGTFRfRVBTSUxPTiAvIDIgKi8KICBGICgxLjAwMDAwMDE3ODgxMzkzNDMyNjE3MTg3NSwg
MHgxLjAwMDAwNHArMEwpLAogIEYgKDEuMDAwMDAwMTc4ODEzOTM0MzI2MTcxODc1MDEsIDB4MS4w
MDAwMDRwKzBMKSwKICAvKiAxLjAgKyAyICogRkxUX0VQU0lMT04gKi8KICBGICgxLjAwMDAwMDIz
ODQxODU3OTEwMTU2MjUsIDB4MS4wMDAwMDRwKzBMKSwKICAvKiAxLjAgKiAweDEucC02MyAqLwog
IEYgKDEuMDg0MjAyMTcyNDg1NTA0NDM0MDA3NDUyODAwODY5OTQxNzExNDI1NzgxMjVlLTE5LCAw
eDEuMHAtNjNMKSwKICBGICgxLjA4NDIwMjIzNzEwODk4OTc4OTcxMjczOTkwMDE5ODc0NTc3OTM5
MTYyOTE4NDgyOTA3MTE2NDEzMTE2NDU1MDc4MTI0OTllLTE5LCAweDEuMHAtNjNMKSwKICAvKiAo
MS4wICsgRkxUX0VQU0lMT04gLyAyKSAqIDB4MS5wLTYzICAqLwogIEYgKDEuMDg0MjAyMjM3MTA4
OTg5Nzg5NzEyNzM5OTAwMTk4NzQ1Nzc5MzkxNjI5MTg0ODI5MDcxMTY0MTMxMTY0NTUwNzgxMjVl
LTE5LCAweDEuMHAtNjNMKSwKICBGICgxLjA4NDIwMjIzNzEwODk4OTc4OTcxMjczOTkwMDE5ODc0
NTc3OTM5MTYyOTE4NDgyOTA3MTE2NDEzMTE2NDU1MDc4MTI1MDFlLTE5LCAweDEuMDAwMDAycC02
M0wpLAogIC8qICgxLjAgKyBGTFRfRVBTSUxPTikgKiAweDEucC02MyAgKi8KICBGICgxLjA4NDIw
MjMwMTczMjQ3NTE0NTQxODAyNjk5OTUyNzU0OTg0NzM1NzQ3NzExOTY1ODE0MjMyODI2MjMyOTEw
MTU2MjVlLTE5LCAweDEuMDAwMDAycC02M0wpLAogIEYgKDEuMDg0MjAyMzY2MzU1OTYwNTAxMTIz
MzE0MDk4ODU2MzUzOTE1MzIzMzI1MDU0NDg3MjEzNDkyMzkzNDkzNjUyMzQzNzQ5OWUtMTksIDB4
MS4wMDAwMDJwLTYzTCksCiAgLyogKDEuMCArIDMgKiBGTFRfRVBTSUxPTiAvIDIpICogMHgxLnAt
NjMgICovCiAgRiAoMS4wODQyMDIzNjYzNTU5NjA1MDExMjMzMTQwOTg4NTYzNTM5MTUzMjMzMjUw
NTQ0ODcyMTM0OTIzOTM0OTM2NTIzNDM3NWUtMTksIDB4MS4wMDAwMDRwLTYzTCksCiAgRiAoMS4w
ODQyMDIzNjYzNTU5NjA1MDExMjMzMTQwOTg4NTYzNTM5MTUzMjMzMjUwNTQ0ODcyMTM0OTIzOTM0
OTM2NTIzNDM3NTAxZS0xOSwgMHgxLjAwMDAwNHAtNjNMKSwKICAvKiAoMS4wICsgMiAqIEZMVF9F
UFNJTE9OKSAqIDB4MS5wLTYzICAqLwogIEYgKDEuMDg0MjAyNDMwOTc5NDQ1ODU2ODI4NjAxMTk4
MTg1MTU3OTgzMjg5MTcyOTg5MzE2Mjg0NjU2NTI0NjU4MjAzMTI1ZS0xOSwgMHgxLjAwMDAwNHAt
NjNMKSwKICAvKiAxLjAgKiAweDEucC0xMjAgKi8KICBGICg3LjUyMzE2Mzg0NTI2MjY0MDA1MDk5
OTkxMzgzODIyMjM3MjMzODAzOTQ1OTU2MzM0MTM2MDEzNzY1NjAxMDkyMDE4MTg3MDQ2MDUxMDI1
MzkwNjI1ZS0zNywgMHgxLjBwLTEyMEwpLAogIEYgKDcuNTIzMTY0MjkzNjc4MTQ4NjM0OTQxMzc2
NTMzODE1ODM4OTkwODEyNjIxNTczMDI1MTgxNTM4MTQxMDU3ODgyNDQzNzIxMzA1MjQzNDAwMzY1
NzI1MzkyNDc1NzI0MjIwMjc1ODc4OTA2MjQ5OWUtMzcsIDB4MS4wcC0xMjBMKSwKICAvKiAoMS4w
ICsgRkxUX0VQU0lMT04gLyAyKSAqIDB4MS5wLTEyMCAgKi8KICBGICg3LjUyMzE2NDI5MzY3ODE0
ODYzNDk0MTM3NjUzMzgxNTgzODk5MDgxMjYyMTU3MzAyNTE4MTUzODE0MTA1Nzg4MjQ0MzcyMTMw
NTI0MzQwMDM2NTcyNTM5MjQ3NTcyNDIyMDI3NTg3ODkwNjI1ZS0zNywgMHgxLjBwLTEyMEwpLAog
IEYgKDcuNTIzMTY0MjkzNjc4MTQ4NjM0OTQxMzc2NTMzODE1ODM4OTkwODEyNjIxNTczMDI1MTgx
NTM4MTQxMDU3ODgyNDQzNzIxMzA1MjQzNDAwMzY1NzI1MzkyNDc1NzI0MjIwMjc1ODc4OTA2MjUw
MWUtMzcsIDB4MS4wMDAwMDJwLTEyMEwpLAogIC8qICgxLjAgKyBGTFRfRVBTSUxPTikgKiAweDEu
cC0xMjAgICovCiAgRiAoNy41MjMxNjQ3NDIwOTM2NTcyMTg4ODI4MzkyMjk0MDkzMDU2NDM1ODU3
ODM1ODI3MDkwMDI5Mzg2MjYxMDQ4NDQ3MDU1NzIxNDk5NzY1NDY4MjUyMDA3ODQ5NTE0NDg0NDA1
NTE3NTc4MTI1ZS0zNywgMHgxLjAwMDAwMnAtMTIwTCksCiAgRiAoNy41MjMxNjUxOTA1MDkxNjU4
MDI4MjQzMDE5MjUwMDI3NzIyOTYzNTg5NDU1OTIzOTI4MjQzMzkxMTExNTE4MDY5Njc0MjI5OTQ3
MDk2OTMyODQ2NzYxNzc0MjcxNzI2NjA4Mjc2MzY3MTg3NDk5ZS0zNywgMHgxLjAwMDAwMnAtMTIw
TCksCiAgLyogKDEuMCArIDMgKiBGTFRfRVBTSUxPTiAvIDIpICogMHgxLnAtMTIwICAqLwogIEYg
KDcuNTIzMTY1MTkwNTA5MTY1ODAyODI0MzAxOTI1MDAyNzcyMjk2MzU4OTQ1NTkyMzkyODI0MzM5
MTExMTUxODA2OTY3NDIyOTk0NzA5NjkzMjg0Njc2MTc3NDI3MTcyNjYwODI3NjM2NzE4NzVlLTM3
LCAweDEuMDAwMDA0cC0xMjBMKSwKICBGICg3LjUyMzE2NTE5MDUwOTE2NTgwMjgyNDMwMTkyNTAw
Mjc3MjI5NjM1ODk0NTU5MjM5MjgyNDMzOTExMTE1MTgwNjk2NzQyMjk5NDcwOTY5MzI4NDY3NjE3
NzQyNzE3MjY2MDgyNzYzNjcxODc1MDFlLTM3LCAweDEuMDAwMDA0cC0xMjBMKSwKICAvKiAoMS4w
ICsgMiAqIEZMVF9FUFNJTE9OKSAqIDB4MS5wLTEyMCAgKi8KICBGICg3LjUyMzE2NTYzODkyNDY3
NDM4Njc2NTc2NDYyMDU5NjIzODk0OTEzMjEwNzYwMjA3NjY0NTczOTU5NjE5ODc2OTIyOTI3Mzgz
OTQ0MjgzOTc0NDE1MTU2OTkwMjg5Njg4MTEwMzUxNTYyNWUtMzcsIDB4MS4wMDAwMDRwLTEyMEwp
LAp9OwojZGVmaW5lIE5URVNUUyAoc2l6ZW9mICh0ZXN0cykgLyBzaXplb2YgKHRlc3RzWzBdKSkK
CgppbnQKbWFpbiAodm9pZCkKewogIGludCBzdGF0dXMgPSAwOwoKICBmb3IgKGludCBpID0gMDsg
aSA8IE5URVNUUzsgKytpKQogICAgewogICAgICBjaGFyICplcDsKICAgICAgbG9uZyBkb3VibGUg
cjsKICAgICAgc3dpdGNoICh0ZXN0c1tpXS50eXBlKQogICAgICAgIHsKICAgICAgICBjYXNlICdm
JzoKICAgICAgICAgIHIgPSBzdHJ0b2YgKHRlc3RzW2ldLnN0ciwgJmVwKTsKICAgICAgICAgIGJy
ZWFrOwogICAgICAgIGNhc2UgJ2QnOgogICAgICAgICAgciA9IHN0cnRvZCAodGVzdHNbaV0uc3Ry
LCAmZXApOwogICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSAnbCc6CiAgICAgICAgICByID0g
c3RydG9sZCAodGVzdHNbaV0uc3RyLCAmZXApOwogICAgICAgICAgYnJlYWs7CiAgICAgICAgZGVm
YXVsdDoKICAgICAgICAgIGFib3J0ICgpOwogICAgICAgIH0KCiAgICAgIGlmICgqZXAgIT0gJ1ww
JykKCXsKCSAgcHJpbnRmICgiJWQ6IHJlc3Qgb2Ygc3RyaW5nIFwiJXNcIlxuIiwgZXApOwoJICBz
dGF0dXMgPSAxOwoJfQoKICAgICAgaWYgKHIgIT0gdGVzdHNbaV0uZXhwZWN0ZWQpCgl7CgkgIHBy
aW50ZiAoIiVkOiBnb3Qgd3JvbmcgcmVzdWx0cyAlLjMwTGEsIGV4cGVjdGVkICUuMzBMYVxuIiwK
CQkgIGksIHIsIHRlc3RzW2ldLmV4cGVjdGVkKTsKCSAgc3RhdHVzID0gMTsKCX0KCiAgICAgIGlm
ICh0ZXN0c1tpXS5jICE9IHRlc3RzW2ldLmV4cGVjdGVkKQoJewoJICBwcmludGYgKCIlZDogYyAl
LjMwTGEsIGV4cGVjdGVkICUuMzBMYVxuIiwKCQkgIGksIHRlc3RzW2ldLmMsIHRlc3RzW2ldLmV4
cGVjdGVkKTsKCSAgc3RhdHVzID0gMTsKCX0KICAgIH0KCiAgcmV0dXJuIHN0YXR1czsKfQo=