c++/1099: g++ -O3 optimization bug found, test case included.

[mdejong at redhat dot com]

>Number:         1099
>Category:       c++
>Synopsis:       g++ -O3 optimization bug found, test case included.
>Confidential:   no
>Severity:       critical
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Dec 19 16:16:00 PST 2000
>Closed-Date:
>Last-Modified:
>Originator:     mdejong@redhat.com
>Release:        unknown-1.0
>Organization:
>Environment:

>Description:
I have found a bug that has something to do with
inlining of C++ methods inside of a file. It only
shows up when you use -O3, things are fine with -O2.

I ran this on a Red Hat 6.2 box (Intel). If you
run on a little endian system, you will need to
comment the WORDS_BIGENDIAN define at the top of
the attached file.

Here are the results I am seeing, this is
with g++ from the egcs CVS as of Dec 11 2000.

% g++ -g -O2 -o long_bug long_bug.cpp

% ./long_bug             
RETURNING cfc00000
RETURNED  cfc00000
OK

% g++ -g -O3 -o long_bug long_bug.cpp

% ./long_bug
RETURNING 1dd00000
RETURNED  1dd00000
ERROR 5.368624e+09


Note, that you can get this test case
to work with -O3 if you move the definition
of the double ULongInt::Double() method
before the others, to do that you would
simply uncomment the #defin USE_WORKAROUND
that the very top of the file.

After some poking around in gdb, it looks
to me like the problem has something to
do with inlining of C++ operators in the
"double ULongInt::Double()" method.


The method looks like this:

double ULongInt::Double()
{
    double val = 0.0,
           multiplier = 1.0;
    ULongInt num = *this;

    while (num > 0)
    {
        val += (multiplier * (num % 10).LowWord());
        num /= 10;
        multiplier *= 10.0;
        //printf("%e\n", val);
    }

    printf("RETURNING %lx\n", val);
    return val;
}


The num variable is set correctly at
the start of the loop, but during the
loop things go wacky. If you jump
in there with gdb, the calculation
look fine as the loop runs, but
before it finishes the results get
hosed somehow.

It might be a problem with underflow,
but I am not sure. It is kind of hard
to figure out what it going on in the
loop because adding an extra operation
can "fix" the problem. For example,
uncommenting the printf inside the
loop makes the error go away.

This problem seems to be recent. I tested
it with egcs-2.91.66 and gcc-2.96 (Red Hat 7.0)
and those were both fine.
>How-To-Repeat:
See desc.
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: application/octet-stream; name="long_bug.cpp"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="long_bug.cpp"

Ly8gJElkOiBsb25nLmNwcCx2IDEuMTYgMjAwMC8wNy8yNSAxMTozMjozMyBtZGVqb25nIEV4cCAk
Ci8vCi8vIFRoaXMgc29mdHdhcmUgaXMgc3ViamVjdCB0byB0aGUgdGVybXMgb2YgdGhlIElCTSBK
aWtlcyBDb21waWxlcgovLyBMaWNlbnNlIEFncmVlbWVudCBhdmFpbGFibGUgYXQgdGhlIGZvbGxv
d2luZyBVUkw6Ci8vIGh0dHA6Ly93d3cuaWJtLmNvbS9yZXNlYXJjaC9qaWtlcy4KLy8gQ29weXJp
Z2h0IChDKSAxOTk2LCAxOTk4LCBJbnRlcm5hdGlvbmFsIEJ1c2luZXNzIE1hY2hpbmVzIENvcnBv
cmF0aW9uCi8vIGFuZCBvdGhlcnMuICBBbGwgUmlnaHRzIFJlc2VydmVkLgovLyBZb3UgbXVzdCBh
Y2NlcHQgdGhlIHRlcm1zIG9mIHRoYXQgYWdyZWVtZW50IHRvIHVzZSB0aGlzIHNvZnR3YXJlLgoK
CiNpbmNsdWRlIDxzdGRpby5oPgoKLy8gSWYgdGhpcyBpcyBkZWZpbmVkIHRoZW4gdGhlIGJ1ZyB3
b3JrYXJvdW5kIHdpbGwgYmUgdXNlZCAhCgovLyNkZWZpbmUgVVNFX1dPUktBUk9VTkQKCgoKCiNk
ZWZpbmUgV09SRFNfQklHRU5ESUFOCgoKLy8gRGVmaW5pbmcgdGhpcyBhbHNvIG1ha2VzIGF2b2lk
cyB0aGUgYnVnIGJ5Ci8vIHVzaW5nIGJpdCBzaGlmdHMgaW4gcGxhY2Ugb2YgZW5kaWFuIHRlc3Rz
LiAoRG9uJ3QgdXNlKQovLyNkZWZpbmUgSEFWRV9VTlNJR05FRF9MT05HX0xPTkcKCgp0eXBlZGVm
IHVuc2lnbmVkIGludCB1NDsKdHlwZWRlZiBzaWduZWQgaW50IGk0Owp0eXBlZGVmIHVuc2lnbmVk
IHNob3J0IHUyOwp0eXBlZGVmIHNpZ25lZCBzaG9ydCBpMjsKdHlwZWRlZiB1bnNpZ25lZCBjaGFy
IHUxOwp0eXBlZGVmIHNpZ25lZCBjaGFyIGkxOwoKI2lmZGVmIEhBVkVfVU5TSUdORURfTE9OR19M
T05HCnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHU4OwojZW5kaWYKCmNsYXNzIExvbmdJbnQ7
CmNsYXNzIFVMb25nSW50OwoKY2xhc3MgQmFzZUxvbmcKewpwcm90ZWN0ZWQ6CiAgICB1bmlvbgog
ICAgewogICAgICAgIGRvdWJsZSBkb3VibGVfd29yZHM7CiNpZm5kZWYgSEFWRV9VTlNJR05FRF9M
T05HX0xPTkcKICAgICAgICB1NCB3b3JkWzJdOwojZWxzZQogICAgICAgIHU4IHdvcmRzOwojZW5k
aWYgLy8gSEFWRV9VTlNJR05FRF9MT05HX0xPTkcKICAgIH0gdmFsdWU7CgogICAgLy8gU2V0IHRo
ZSBoaWdoIHdvcmQgb25seS4gRG9lcyBub3QgbW9kaWZ5IHRoZSBsb3cgd29yZCEKICAgIGlubGlu
ZSB2b2lkIHNldEhpZ2hXb3JkKHU0IGhpZ2gpIHsKI2lmbmRlZiBIQVZFX1VOU0lHTkVEX0xPTkdf
TE9ORwojIGlmbmRlZiBXT1JEU19CSUdFTkRJQU4KICAgICAgICB2YWx1ZS53b3JkWzFdID0gaGln
aDsKIyBlbHNlCiAgICAgICAgdmFsdWUud29yZFswXSA9IGhpZ2g7CiMgZW5kaWYKI2Vsc2UKICAg
ICAgICBzZXRIaWdoQW5kTG93V29yZHMoaGlnaCwgTG93V29yZCgpKTsKI2VuZGlmIC8vIEhBVkVf
VU5TSUdORURfTE9OR19MT05HCiAgICB9CgogICAgLy8gU2V0IHRoZSBsb3cgd29yZCBvbmx5LiBE
b2VzIG5vdCBtb2RpZnkgdGhlIGhpZ2ggd29yZCEKICAgIGlubGluZSB2b2lkIHNldExvd1dvcmQo
dTQgbG93KSB7CiNpZm5kZWYgSEFWRV9VTlNJR05FRF9MT05HX0xPTkcKIyBpZm5kZWYgV09SRFNf
QklHRU5ESUFOCiAgICAgICAgdmFsdWUud29yZFswXSA9IGxvdzsKIyBlbHNlCiAgICAgICAgdmFs
dWUud29yZFsxXSA9IGxvdzsKIyBlbmRpZgojZWxzZQogICAgICAgIHNldEhpZ2hBbmRMb3dXb3Jk
cyhIaWdoV29yZCgpLCBsb3cpOwojZW5kaWYgLy8gSEFWRV9VTlNJR05FRF9MT05HX0xPTkcKICAg
IH0KICAgIAogICAgLy8gU2V0IHRoZSB2YWx1ZSBmb3IgYm90aCB3b3Jkcy4KICAgIGlubGluZSB2
b2lkIHNldEhpZ2hBbmRMb3dXb3Jkcyh1NCBoaWdoLCB1NCBsb3cpIHsKI2lmbmRlZiBIQVZFX1VO
U0lHTkVEX0xPTkdfTE9ORwojIGlmbmRlZiBXT1JEU19CSUdFTkRJQU4KICAgICAgICB2YWx1ZS53
b3JkWzFdID0gaGlnaDsKICAgICAgICB2YWx1ZS53b3JkWzBdID0gbG93OwojIGVsc2UKICAgICAg
ICB2YWx1ZS53b3JkWzBdID0gaGlnaDsKICAgICAgICB2YWx1ZS53b3JkWzFdID0gbG93OwojIGVu
ZGlmCiNlbHNlCiAgICAgICAgdmFsdWUud29yZHMgPSAoKCh1OCkgaGlnaCkgPDwgMzIpIHwgbG93
OwojZW5kaWYgLy8gSEFWRV9VTlNJR05FRF9MT05HX0xPTkcKICAgIH0KCnB1YmxpYzoKCiNpZm5k
ZWYgSEFWRV9VTlNJR05FRF9MT05HX0xPTkcKIyBpZm5kZWYgV09SRFNfQklHRU5ESUFOCiAgICBp
bmxpbmUgdTQgSGlnaFdvcmQoKSB7IHJldHVybiB2YWx1ZS53b3JkWzFdOyB9CiAgICBpbmxpbmUg
dTQgTG93V29yZCgpICB7IHJldHVybiB2YWx1ZS53b3JkWzBdOyB9CiMgZWxzZQogICAgaW5saW5l
IHU0IEhpZ2hXb3JkKCkgeyByZXR1cm4gdmFsdWUud29yZFswXTsgfQogICAgaW5saW5lIHU0IExv
d1dvcmQoKSAgeyByZXR1cm4gdmFsdWUud29yZFsxXTsgfQojIGVuZGlmCiNlbHNlCiAgICBpbmxp
bmUgdTQgSGlnaFdvcmQoKSB7IHJldHVybiAoKHU0KSAodmFsdWUud29yZHMgPj4gMzIpKTsgfQog
ICAgaW5saW5lIHU0IExvd1dvcmQoKSAgeyByZXR1cm4gKCh1NCkgdmFsdWUud29yZHMpOyB9CiNl
bmRpZiAvLyBIQVZFX1VOU0lHTkVEX0xPTkdfTE9ORwoKICAgIGRvdWJsZSBEb3VibGVWaWV3KCkg
eyByZXR1cm4gdmFsdWUuZG91YmxlX3dvcmRzOyB9CgogICAgQmFzZUxvbmcodTQgaGlnaCwgdTQg
bG93KTsKICAgIEJhc2VMb25nKHU0IGEpOwogICAgQmFzZUxvbmcoaTQgYSk7CiAgICBpbmxpbmUg
QmFzZUxvbmcgKHZvaWQpIHt9CgogICAgQmFzZUxvbmcgIG9wZXJhdG9yKyAgKEJhc2VMb25nKTsg
Ly8gYmluYXJ5IGFkZGl0aW9uCiAgICBCYXNlTG9uZyAgb3BlcmF0b3IrICAoKTsgICAgICAgICAv
LyB1bmFyeSBwbHVzCiAgICBCYXNlTG9uZyYgb3BlcmF0b3IrPSAoQmFzZUxvbmcpOyAvLyBhZGQg
YW5kIGFzc2lnbgoKICAgIEJhc2VMb25nICBvcGVyYXRvci0gIChCYXNlTG9uZyk7IC8vIGJpbmFy
eSBzdWJ0cmFjdGlvbgogICAgQmFzZUxvbmcgIG9wZXJhdG9yLSAgKCk7ICAgICAgICAgLy8gdW5h
cnkgbWludXMKICAgIEJhc2VMb25nJiBvcGVyYXRvci09IChCYXNlTG9uZyk7IC8vIHN1YnRyYWN0
IGFuZCBhc3NpZ24KCiAgICBCYXNlTG9uZyAgb3BlcmF0b3IqIChCYXNlTG9uZyk7ICAvLyBtdWx0
aXBsaWNhdGlvbgogICAgQmFzZUxvbmcmIG9wZXJhdG9yKj0oQmFzZUxvbmcpOyAgLy8gbXVsdGlw
bHkgYW5kIGFzc2lnbgoKICAgIEJhc2VMb25nICBvcGVyYXRvcjw8IChCYXNlTG9uZyk7IC8vIGxl
ZnQgc2hpZnQKICAgIEJhc2VMb25nJiBvcGVyYXRvcjw8PShCYXNlTG9uZyk7IC8vIGxlZnQgc2hp
ZnQgYW5kIGFzc2lnbgoKICAgIGJvb2wgICAgICBvcGVyYXRvcj09IChCYXNlTG9uZyk7IC8vIGVx
dWFsCgogICAgQmFzZUxvbmcgIG9wZXJhdG9yfiAgKCk7ICAgICAgICAgLy8gYml0d2lzZSBjb21w
bGVtZW50CgogICAgc3RhdGljIHZvaWQgRGl2aWRlKEJhc2VMb25nLCBCYXNlTG9uZywgQmFzZUxv
bmcgJiwgQmFzZUxvbmcgJik7CgogICAgb3BlcmF0b3IgTG9uZ0ludCgpOyAgICAgICAgICAgICAg
ICAgLy8gQ2FzdCB0byBMb25nSW50CiAgICBvcGVyYXRvciBVTG9uZ0ludCgpOyAgICAgICAgICAg
ICAgICAvLyBDYXN0IHRvIFVMb25nSW50Cn07CgoKY2xhc3MgTG9uZ0ludCA6IHB1YmxpYyBCYXNl
TG9uZwp7CnB1YmxpYzoKCiAgICBpbmxpbmUgTG9uZ0ludCAodTQgYSwgdTQgYikgOiBCYXNlTG9u
ZyAoYSwgYikge30KICAgIGlubGluZSBMb25nSW50ICh1NCBhKSA6IEJhc2VMb25nIChhKSB7fQog
ICAgaW5saW5lIExvbmdJbnQgKGk0IGEpIDogQmFzZUxvbmcgKGEpIHt9CiAgICBpbmxpbmUgTG9u
Z0ludCAodm9pZCkgOiBCYXNlTG9uZyAoKSB7fQoKICAgIExvbmdJbnQgIG9wZXJhdG9yLyAgKExv
bmdJbnQpOyAvLyBkaXZpZGUKICAgIExvbmdJbnQmIG9wZXJhdG9yLz0gKExvbmdJbnQpOyAvLyBk
aXZpZGUgYW5kIGFzc2lnbgoKICAgIExvbmdJbnQgIG9wZXJhdG9yJSAgKExvbmdJbnQpOyAvLyBt
b2R1bHVzCgogICAgYm9vbCAgb3BlcmF0b3I8ICAoTG9uZ0ludCk7IC8vIGxlc3MtdGhhbgogICAg
Ym9vbCAgb3BlcmF0b3I+ICAoTG9uZ0ludCk7IC8vIGdyZWF0ZXItdGhhbgogICAgYm9vbCAgb3Bl
cmF0b3I8PSAoTG9uZ0ludCk7IC8vIGxlc3MtdGhhbiBvciBlcXVhbAogICAgYm9vbCAgb3BlcmF0
b3I+PSAoTG9uZ0ludCk7IC8vIGdyZWF0ZXItdGhhbiBvciBlcXVhbAoKICAgIGRvdWJsZSBEb3Vi
bGUoKTsgICAgICAgICAgIC8vIGNvbnZlcnQgVUxvbmdJbnQgdmFsdWUgdG8gYSBkb3VibGUgdmFs
dWUKfTsKCgpjbGFzcyBVTG9uZ0ludCA6IHB1YmxpYyBCYXNlTG9uZwp7CnB1YmxpYzoKCiAgICBp
bmxpbmUgVUxvbmdJbnQgKHU0IGEsIHU0IGIpIDogQmFzZUxvbmcgKGEsIGIpIHt9CiAgICBpbmxp
bmUgVUxvbmdJbnQgKHU0IGEpIDogQmFzZUxvbmcgKGEpIHt9CiAgICBpbmxpbmUgVUxvbmdJbnQg
KGk0IGEpIDogQmFzZUxvbmcgKGEpIHt9CiAgICBpbmxpbmUgVUxvbmdJbnQgKHZvaWQpIDogQmFz
ZUxvbmcgKCkge30KCiAgICBVTG9uZ0ludCAgb3BlcmF0b3IvICAoVUxvbmdJbnQpOyAvLyBkaXZp
ZGUKICAgIFVMb25nSW50JiBvcGVyYXRvci89IChVTG9uZ0ludCk7IC8vIGRpdmlkZSBhbmQgYXNz
aWduCgogICAgVUxvbmdJbnQgIG9wZXJhdG9yJSAgKFVMb25nSW50KTsgLy8gbW9kdWx1cwoKICAg
IGJvb2wgICBvcGVyYXRvcjwgIChVTG9uZ0ludCk7IC8vIGxlc3MtdGhhbgogICAgYm9vbCAgIG9w
ZXJhdG9yPiAgKFVMb25nSW50KTsgLy8gZ3JlYXRlci10aGFuCiAgICBib29sICAgb3BlcmF0b3I8
PSAoVUxvbmdJbnQpOyAvLyBsZXNzLXRoYW4gb3IgZXF1YWwKICAgIGJvb2wgICBvcGVyYXRvcj49
IChVTG9uZ0ludCk7IC8vIGdyZWF0ZXItdGhhbiBvciBlcXVhbAoKICAgIGRvdWJsZSBEb3VibGUo
KTsgICAgICAvLyBjb252ZXJ0IExvbmdJbnQgdmFsdWUgdG8gYSBkb3VibGUgdmFsdWUKfTsKCgoK
CgoKLy8gRGVjbGFyaW5nIFVMb25nSW50OjpEb3VibGUoKSBmaXJzdCBtYWtlcyBpdCB3b3JrIC4K
CgojaWZkZWYgVVNFX1dPUktBUk9VTkQKCmRvdWJsZSBVTG9uZ0ludDo6RG91YmxlKCkKewogICAg
ZG91YmxlIHZhbCA9IDAuMCwKICAgICAgICAgICBtdWx0aXBsaWVyID0gMS4wOwogICAgVUxvbmdJ
bnQgbnVtID0gKnRoaXM7CgogICAgd2hpbGUgKG51bSA+IDApCiAgICB7CiAgICAgICAgdmFsICs9
IChtdWx0aXBsaWVyICogKG51bSAlIDEwKS5Mb3dXb3JkKCkpOwogICAgICAgIG51bSAvPSAxMDsK
ICAgICAgICBtdWx0aXBsaWVyICo9IDEwLjA7CiAgICAgICAgLy9wcmludGYoIiVlXG4iLCB2YWwp
OwogICAgfQoKICAgIHByaW50ZigiUkVUVVJOSU5HICVseFxuIiwgdmFsKTsKICAgIHJldHVybiB2
YWw7Cn0KCiNlbmRpZgoKCgpCYXNlTG9uZzo6b3BlcmF0b3IgTG9uZ0ludCgpCnsKICAgIHJldHVy
biBMb25nSW50KEhpZ2hXb3JkKCksIExvd1dvcmQoKSk7Cn0KCkJhc2VMb25nOjpvcGVyYXRvciBV
TG9uZ0ludCgpCnsKICAgIHJldHVybiBVTG9uZ0ludChIaWdoV29yZCgpLCBMb3dXb3JkKCkpOwp9
Cgpib29sIEJhc2VMb25nOjpvcGVyYXRvcj09IChCYXNlTG9uZyBvcCkKewogICAgcmV0dXJuICgo
SGlnaFdvcmQoKSA9PSBvcC5IaWdoV29yZCgpKSAmJiAoTG93V29yZCgpID09IG9wLkxvd1dvcmQo
KSkpOwp9CgpCYXNlTG9uZyBCYXNlTG9uZzo6b3BlcmF0b3J+KCkKewogICAgcmV0dXJuIEJhc2VM
b25nKH5IaWdoV29yZCgpLCB+TG93V29yZCgpKTsKfQoKQmFzZUxvbmcgQmFzZUxvbmc6Om9wZXJh
dG9yPDwgKEJhc2VMb25nIG9wKQp7CiAgICB1NCBuID0gb3AuTG93V29yZCgpOyAvLyBBbHdheXMg
dHJlYXQgdGhpcyB2YWx1ZSBhcyBwb3NpdGl2ZSwgc2luY2UgbmVnYXRpdmUgdmFsdWVzIGFyZSBu
b3QgYWxsb3dlZAoKICAgIC8vCiAgICAvLyBOb3RlIHRoYXQgdGhpcyBmdW5jdGlvbiBhc3N1bWVz
IHRoYXQgZm9yIHR3byAzMi1iaXQgaW50ZWdlcnMKICAgIC8vIHggPDwgeSwgd2hlcmUgeSA9IDAs
IGlzIHdlbGwtZGVmaW5lZCBhbmQgdGhhdCB0aGUgcmVzdWx0IGlzCiAgICAvLyB0aGUgdmFsdWUg
eC4gVGhpcyBpcyB0cnVlIGluIEFuc2ktQyBhbmQgQysrIGJ1dCBub3QgdHJ1ZSBpbgogICAgLy8g
b2xkIHZlcnNpb25zIG9mIEMgKFNlZSBLZXJuaWdoYW4gYW5kIFJpdGNoaWUpLgogICAgLy8gTm90
ZSBhbHNvIHRoYXQgaW4gc2hpZnRpbmcgYSAzMi1iaXQgd29yZCwgaWYgeSA+PSAzMiB0aGVuIHRo
ZQogICAgLy8gcmVzdWx0IGlzIHVucHJlZGljdGFibGUuIE9uIEFpeCwgeGxDIHdpbGwgcHJvZHVj
ZSB0aGUgcmVzdWx0IDAoZ29vZCEpCiAgICAvLyB3aGVyZWFzIG9uIHdpbmRvd3MgdGhlIE1pY3Jv
c29mdCBjb21waWxlciBwcm9kdWNlcyB0aGUgdmFsdWUgb2YgeCh2ZXJ5IGJhZCAhKS4KICAgIC8v
IFRoYXQgaXMgdGhlIHJlYXNvbiB3aHkgd2UgaGF2ZSB0aGUgaW5pdGlhbCBzcGVjaWFsIGNoZWNr
IGZvciAobiA9PSAwKS4KICAgIC8vCgogICAgLy8KICAgIC8vIGdjYy0yLjk1LjEgY29tcGlsZXIg
YnVnIHByZXZlbnRzIHVzZSBvZiB0aGlzIGltcGxlbWVudGF0aW9uLgogICAgLy8gcmV0dXJuIChu
ID09IDAgPyAqdGhpcwogICAgLy8gICAgICAgICAgICAgICAgOiBuIDwgMzIKICAgIC8vICAgICAg
ICAgICAgICAgICAgICA/IEJhc2VMb25nKChIaWdoV29yZCgpIDw8IG4pIHwgKExvd1dvcmQoKSA+
PiAoMzIgLSBuKSksIExvd1dvcmQoKSA8PCBuKQogICAgLy8gICAgICAgICAgICAgICAgICAgIDog
QmFzZUxvbmcoTG93V29yZCgpIDw8IChuIC0gMzIpLCAwKSk7CiAgICAvLwogICAgaWYgKG4gPT0g
MCkKICAgICAgICAgcmV0dXJuICp0aGlzOwogICAgZWxzZSBpZiAobiA8IDMyKQogICAgICAgICBy
ZXR1cm4gQmFzZUxvbmcoKEhpZ2hXb3JkKCkgPDwgbikgfCAoTG93V29yZCgpID4+ICgzMiAtIG4p
KSwgTG93V29yZCgpIDw8IG4pOwogICAgZWxzZSByZXR1cm4gQmFzZUxvbmcoTG93V29yZCgpIDw8
IChuIC0gMzIpLCAwKTsKfQoKQmFzZUxvbmcmIEJhc2VMb25nOjpvcGVyYXRvcjw8PSAoQmFzZUxv
bmcgb3ApCnsKICAgICp0aGlzID0gKnRoaXMgPDwgb3A7CiAgICByZXR1cm4gKnRoaXM7Cn0KCkJh
c2VMb25nIEJhc2VMb25nOjpvcGVyYXRvcisgKEJhc2VMb25nIG9wKQp7CiAgICB1NCB1c2hvcnQx
ID0gKExvd1dvcmQoKSAmIDB4RkZGRikgKyAob3AuTG93V29yZCgpICYgMHhGRkZGKSwKICAgICAg
IHVzaG9ydDIgPSAodXNob3J0MSA+PiAxNikgKyAoTG93V29yZCgpID4+IDE2KSArIChvcC5Mb3dX
b3JkKCkgPj4gMTYpLAogICAgICAgdXNob3J0MyA9ICh1c2hvcnQyID4+IDE2KSArIChIaWdoV29y
ZCgpICYgMHhGRkZGKSArIChvcC5IaWdoV29yZCgpICYgMHhGRkZGKSwKICAgICAgIHVzaG9ydDQg
PSAodXNob3J0MyA+PiAxNikgKyAoSGlnaFdvcmQoKSA+PiAxNikgKyAob3AuSGlnaFdvcmQoKSA+
PiAxNik7CgogICAgcmV0dXJuIEJhc2VMb25nKCh1c2hvcnQzICYgMHhGRkZGKSB8ICh1c2hvcnQ0
IDw8IDE2KSwgKHVzaG9ydDEgJiAweEZGRkYpIHwgKHVzaG9ydDIgPDwgMTYpKTsKfQoKQmFzZUxv
bmcmIEJhc2VMb25nOjpvcGVyYXRvcis9IChCYXNlTG9uZyBvcCkKewogICAgKnRoaXMgPSAqdGhp
cyArIG9wOwogICAgcmV0dXJuICp0aGlzOwp9CgpCYXNlTG9uZyBCYXNlTG9uZzo6b3BlcmF0b3Ir
ICgpCnsKICAgIHJldHVybigqdGhpcyk7Cn0KCkJhc2VMb25nIEJhc2VMb25nOjpvcGVyYXRvci0g
KCkKewogICAgcmV0dXJuIH4oKnRoaXMpICsgMTsKfQoKQmFzZUxvbmcgQmFzZUxvbmc6Om9wZXJh
dG9yLSAoQmFzZUxvbmcgb3ApCnsKICAgIHJldHVybiAqdGhpcyArICgtb3ApOwp9CgpCYXNlTG9u
ZyYgQmFzZUxvbmc6Om9wZXJhdG9yLT0gKEJhc2VMb25nIG9wKQp7CiAgICAqdGhpcyA9ICp0aGlz
IC0gb3A7CiAgICByZXR1cm4gKnRoaXM7Cn0KCkJhc2VMb25nIEJhc2VMb25nOjpvcGVyYXRvciog
KEJhc2VMb25nIG9wKQp7CiAgICB1NCB4MCA9IHRoaXMgLT4gTG93V29yZCgpICAgJiAweEZGRkYs
CiAgICAgICB4MSA9IHRoaXMgLT4gTG93V29yZCgpICA+PiAxNiwKICAgICAgIHgyID0gdGhpcyAt
PiBIaWdoV29yZCgpICAmIDB4RkZGRiwKICAgICAgIHgzID0gdGhpcyAtPiBIaWdoV29yZCgpID4+
IDE2LAoKICAgICAgIHkwID0gb3AuTG93V29yZCgpICAgJiAweEZGRkYsCiAgICAgICB5MSA9IG9w
Lkxvd1dvcmQoKSAgPj4gMTYsCiAgICAgICB5MiA9IG9wLkhpZ2hXb3JkKCkgICYgMHhGRkZGLAog
ICAgICAgeTMgPSBvcC5IaWdoV29yZCgpID4+IDE2OwoKICAgIEJhc2VMb25nIHJlc3VsdCA9IEJh
c2VMb25nKDAsIHgwICogeTApLAogICAgICAgICAgICAgcGFydDEgID0gQmFzZUxvbmcoMCwgeDAg
KiB5MSk7CiAgICBwYXJ0MSAgPDw9ICgxIDw8IDQpOwogICAgcmVzdWx0ICs9IHBhcnQxOwogICAg
QmFzZUxvbmcgcGFydDIgID0gQmFzZUxvbmcoMCwgeDAgKiB5Mik7CiAgICBwYXJ0MiAgPDw9ICgy
IDw8IDQpOwogICAgcmVzdWx0ICs9IHBhcnQyOwogICAgQmFzZUxvbmcgcGFydDMgID0gQmFzZUxv
bmcoMCwgeDAgKiB5Myk7CiAgICBwYXJ0MyAgPDw9ICgzIDw8IDQpOwogICAgcmVzdWx0ICs9IHBh
cnQzOwoKICAgIEJhc2VMb25nIHBhcnQ0ICA9IEJhc2VMb25nKDAsIHgxICogeTApOwogICAgcGFy
dDQgIDw8PSAoMSA8PCA0KTsKICAgIHJlc3VsdCArPSBwYXJ0NDsKICAgIEJhc2VMb25nIHBhcnQ1
ICA9IEJhc2VMb25nKDAsIHgxICogeTEpOwogICAgcGFydDUgIDw8PSAoMiA8PCA0KTsKICAgIHJl
c3VsdCArPSBwYXJ0NTsKICAgIEJhc2VMb25nIHBhcnQ2ICA9IEJhc2VMb25nKDAsIHgxICogeTIp
OwogICAgcGFydDYgIDw8PSAoMyA8PCA0KTsKICAgIHJlc3VsdCArPSBwYXJ0NjsKICAgIEJhc2VM
b25nIHBhcnQ3ICA9IEJhc2VMb25nKDAsIHgxICogeTMpOwogICAgcGFydDcgIDw8PSAoNCA8PCA0
KTsKICAgIHJlc3VsdCArPSBwYXJ0NzsKCiAgICBCYXNlTG9uZyBwYXJ0OCAgPSBCYXNlTG9uZygw
LCB4MiAqIHkwKTsKICAgIHBhcnQ4ICA8PD0gKDIgPDwgNCk7CiAgICByZXN1bHQgKz0gcGFydDg7
CiAgICBCYXNlTG9uZyBwYXJ0OSAgPSBCYXNlTG9uZygwLCB4MiAqIHkxKTsKICAgIHBhcnQ5ICA8
PD0gKDMgPDwgNCk7CiAgICByZXN1bHQgKz0gcGFydDk7CiAgICBCYXNlTG9uZyBwYXJ0MTAgPSBC
YXNlTG9uZygwLCB4MiAqIHkyKTsKICAgIHBhcnQxMCA8PD0gKDQgPDwgNCk7CiAgICByZXN1bHQg
Kz0gcGFydDEwOwogICAgQmFzZUxvbmcgcGFydDExID0gQmFzZUxvbmcoMCwgeDIgKiB5Myk7CiAg
ICBwYXJ0MTEgPDw9ICg1IDw8IDQpOwogICAgcmVzdWx0ICs9IHBhcnQxMTsKCiAgICBCYXNlTG9u
ZyBwYXJ0MTIgPSBCYXNlTG9uZygwLCB4MyAqIHkwKTsKICAgIHBhcnQxMiA8PD0gKDMgPDwgNCk7
CiAgICByZXN1bHQgKz0gcGFydDEyOwogICAgQmFzZUxvbmcgcGFydDEzID0gQmFzZUxvbmcoMCwg
eDMgKiB5MSk7CiAgICBwYXJ0MTMgPDw9ICg0IDw8IDQpOwogICAgcmVzdWx0ICs9IHBhcnQxMzsK
ICAgIEJhc2VMb25nIHBhcnQxNCA9IEJhc2VMb25nKDAsIHgzICogeTIpOwogICAgcGFydDE0IDw8
PSAoNSA8PCA0KTsKICAgIHJlc3VsdCArPSBwYXJ0MTQ7CiAgICBCYXNlTG9uZyBwYXJ0MTUgPSBC
YXNlTG9uZygwLCB4MyAqIHkzKTsKICAgIHBhcnQxNSA8PD0gKDYgPDwgNCk7CiAgICByZXN1bHQg
Kz0gcGFydDE1OwoKICAgIHJldHVybiByZXN1bHQ7Cn0KCkJhc2VMb25nJiBCYXNlTG9uZzo6b3Bl
cmF0b3IqPSAoQmFzZUxvbmcgb3ApCnsKICAgICp0aGlzID0gKnRoaXMgKiBvcDsKICAgIHJldHVy
biAqdGhpczsKfQoKCkJhc2VMb25nOjpCYXNlTG9uZyh1NCBoaWdoLCB1NCBsb3cpCnsKICAgIHNl
dEhpZ2hBbmRMb3dXb3JkcyhoaWdoLCBsb3cpOwp9CgpCYXNlTG9uZzo6QmFzZUxvbmcodTQgYSkK
ewogICAgc2V0SGlnaEFuZExvd1dvcmRzKDAsIGEpOwp9CgpCYXNlTG9uZzo6QmFzZUxvbmcoaTQg
YSkKewogICAgLy8KICAgIC8vIFNpbmNlIHRoZSBjYXJyeSBiaXQgaXMgbm90IGd1YXJhbnRlZWQg
dG8gcmlwcGxlLCB3ZSBjYW5ub3QgdXNlIHRoaXMgY29kZS4KICAgIC8vCiAgICAvLyAgICAgICAg
YSA8PCAzMTsKICAgIC8vCiAgICBzZXRIaWdoQW5kTG93V29yZHMoYSA8IDAgPyAweEZGRkZGRkZG
IDogMHgwMDAwMDAwMCwgYSk7Cn0KCgp2b2lkIEJhc2VMb25nOjpEaXZpZGUoQmFzZUxvbmcgZGl2
aWRlbmQsIEJhc2VMb25nIGRpdmlzb3IsIEJhc2VMb25nICZxdW90aWVudCwgQmFzZUxvbmcgJnJl
bWFpbmRlcikKewogICAgdTQgaGlnaCA9IGRpdmlkZW5kLkhpZ2hXb3JkKCksCiAgICAgICBsb3cg
ID0gZGl2aWRlbmQuTG93V29yZCgpLAogICAgICAgcmVtYWluZGVyX2hpZ2ggPSAwOwoKICAgIGZv
ciAoaW50IGkgPSAwOyBpIDwgMzI7IGkrKykKICAgIHsKICAgICAgICByZW1haW5kZXJfaGlnaCA9
IChyZW1haW5kZXJfaGlnaCA8PCAxKSB8IChoaWdoID4+IDMxKTsKICAgICAgICBoaWdoIDw8PSAx
OwogICAgICAgIGlmICgoVUxvbmdJbnQpIGRpdmlzb3IgPD0gcmVtYWluZGVyX2hpZ2gpCiAgICAg
ICAgewogICAgICAgICAgICBoaWdoKys7CiAgICAgICAgICAgIHJlbWFpbmRlcl9oaWdoIC09IGRp
dmlzb3IuTG93V29yZCgpOwogICAgICAgIH0KICAgIH0KCiAgICByZW1haW5kZXIgPSBCYXNlTG9u
ZygwLCByZW1haW5kZXJfaGlnaCk7CgogICAgZm9yIChpbnQgaiA9IDA7IGogPCAzMjsgaisrKQog
ICAgewogICAgICAgIHJlbWFpbmRlciA8PD0gMTsKICAgICAgICByZW1haW5kZXIuc2V0TG93V29y
ZChyZW1haW5kZXIuTG93V29yZCgpIHwgKGxvdyA+PiAzMSkpOwogICAgICAgIGxvdyA8PD0gMTsK
ICAgICAgICBpZiAoKFVMb25nSW50KSBkaXZpc29yIDw9IHJlbWFpbmRlcikKICAgICAgICB7CiAg
ICAgICAgICAgIGxvdysrOwogICAgICAgICAgICByZW1haW5kZXIgLT0gZGl2aXNvcjsKICAgICAg
ICB9CiAgICB9CgogICAgcXVvdGllbnQgPSBCYXNlTG9uZyhoaWdoLCBsb3cpOwoKICAgIHJldHVy
bjsKfQoKClVMb25nSW50JiBVTG9uZ0ludDo6b3BlcmF0b3IvPSAoVUxvbmdJbnQgb3ApCnsKICAg
ICp0aGlzID0gKnRoaXMgLyBvcDsKICAgIHJldHVybiAqdGhpczsKfQoKClVMb25nSW50IFVMb25n
SW50OjpvcGVyYXRvci8gKFVMb25nSW50IG9wKQp7CiAgICBCYXNlTG9uZyBxdW90aWVudCwKICAg
ICAgICAgICAgIHJlbWFpbmRlcjsKCiAgICBEaXZpZGUoKnRoaXMsIG9wLCBxdW90aWVudCwgcmVt
YWluZGVyKTsKCiAgICByZXR1cm4gcXVvdGllbnQ7Cn0KClVMb25nSW50IFVMb25nSW50OjpvcGVy
YXRvciUgKFVMb25nSW50IG9wKQp7CiAgICBCYXNlTG9uZyBxdW90aWVudCwKICAgICAgICAgICAg
IHJlbWFpbmRlcjsKCiAgICBEaXZpZGUoKnRoaXMsIG9wLCBxdW90aWVudCwgcmVtYWluZGVyKTsK
CiAgICByZXR1cm4gcmVtYWluZGVyOwp9Cgpib29sIFVMb25nSW50OjpvcGVyYXRvcjwgKFVMb25n
SW50IG9wKQp7CiAgICByZXR1cm4gKEhpZ2hXb3JkKCkgPT0gb3AuSGlnaFdvcmQoKSA/IExvd1dv
cmQoKSA8IG9wLkxvd1dvcmQoKSA6IEhpZ2hXb3JkKCkgPCBvcC5IaWdoV29yZCgpKTsKfQoKYm9v
bCBVTG9uZ0ludDo6b3BlcmF0b3I8PSAoVUxvbmdJbnQgb3ApCnsKICAgIHJldHVybiAoSGlnaFdv
cmQoKSA9PSBvcC5IaWdoV29yZCgpID8gTG93V29yZCgpIDw9IG9wLkxvd1dvcmQoKSA6IEhpZ2hX
b3JkKCkgPD0gb3AuSGlnaFdvcmQoKSk7Cn0KCmJvb2wgVUxvbmdJbnQ6Om9wZXJhdG9yPiAoVUxv
bmdJbnQgb3ApCnsKICAgIHJldHVybiAoSGlnaFdvcmQoKSA9PSBvcC5IaWdoV29yZCgpID8gTG93
V29yZCgpID4gb3AuTG93V29yZCgpIDogSGlnaFdvcmQoKSA+IG9wLkhpZ2hXb3JkKCkpOwp9Cgpi
b29sIFVMb25nSW50OjpvcGVyYXRvcj49IChVTG9uZ0ludCBvcCkKewogICAgcmV0dXJuIChIaWdo
V29yZCgpID09IG9wLkhpZ2hXb3JkKCkgPyBMb3dXb3JkKCkgPj0gb3AuTG93V29yZCgpIDogSGln
aFdvcmQoKSA+PSBvcC5IaWdoV29yZCgpKTsKfQoKTG9uZ0ludCBMb25nSW50OjpvcGVyYXRvci8g
KExvbmdJbnQgb3ApCnsKICAgIGJvb2wgbmVnYXRpdmVfZGl2aWRlbmQgPSAoKEhpZ2hXb3JkKCkg
JiAweDgwMDAwMDAwKSAhPSAwKSwKICAgICAgICAgbmVnYXRpdmVfZGl2aXNvciAgPSAoKG9wLkhp
Z2hXb3JkKCkgJiAweDgwMDAwMDAwKSAhPSAwKTsKCiAgICBCYXNlTG9uZyBhID0gKG5lZ2F0aXZl
X2RpdmlkZW5kID8gLSgqdGhpcykgOiArKCp0aGlzKSksCiAgICAgICAgICAgICBiID0gKG5lZ2F0
aXZlX2Rpdmlzb3IgID8gLShvcCkgICAgOiArKG9wKSksCiAgICAgICAgICAgICBxdW90aWVudCwK
ICAgICAgICAgICAgIHJlbWFpbmRlcjsKCiAgICBEaXZpZGUoYSwgYiwgcXVvdGllbnQsIHJlbWFp
bmRlcik7CgogICAgcmV0dXJuIChuZWdhdGl2ZV9kaXZpZGVuZCBeIG5lZ2F0aXZlX2Rpdmlzb3Ig
PyAtcXVvdGllbnQgOiBxdW90aWVudCk7Cn0KCkxvbmdJbnQmIExvbmdJbnQ6Om9wZXJhdG9yLz0g
KExvbmdJbnQgb3ApCnsKICAgICp0aGlzID0gKnRoaXMgLyBvcDsKICAgIHJldHVybiAqdGhpczsK
fQoKTG9uZ0ludCBMb25nSW50OjpvcGVyYXRvciUgKExvbmdJbnQgb3ApCnsKICAgIGJvb2wgbmVn
YXRpdmVfZGl2aWRlbmQgPSAoKEhpZ2hXb3JkKCkgJiAweDgwMDAwMDAwKSAhPSAwKSwKICAgIG5l
Z2F0aXZlX2Rpdmlzb3IgID0gKChvcC5IaWdoV29yZCgpICYgMHg4MDAwMDAwMCkgIT0gMCk7Cgog
ICAgQmFzZUxvbmcgYSA9IChuZWdhdGl2ZV9kaXZpZGVuZCA/IC0oKnRoaXMpIDogKygqdGhpcykp
LAogICAgICAgICAgICAgYiA9IChuZWdhdGl2ZV9kaXZpc29yICA/IC0ob3ApICAgIDogKyhvcCkp
LAogICAgICAgICAgICAgcXVvdGllbnQsCiAgICAgICAgICAgICByZW1haW5kZXI7CgogICAgRGl2
aWRlKGEsIGIsIHF1b3RpZW50LCByZW1haW5kZXIpOwoKICAgIHJldHVybiAobmVnYXRpdmVfZGl2
aWRlbmQgPyAtcmVtYWluZGVyIDogcmVtYWluZGVyKTsKfQoKYm9vbCBMb25nSW50OjpvcGVyYXRv
cjwgKExvbmdJbnQgb3ApCnsKICAgIHJldHVybiAoSGlnaFdvcmQoKSA9PSBvcC5IaWdoV29yZCgp
ID8gTG93V29yZCgpIDwgb3AuTG93V29yZCgpIDogKGk0KSBIaWdoV29yZCgpIDwgKGk0KSBvcC5I
aWdoV29yZCgpKTsKfQoKYm9vbCBMb25nSW50OjpvcGVyYXRvcjw9IChMb25nSW50IG9wKQp7CiAg
ICByZXR1cm4gKEhpZ2hXb3JkKCkgPT0gb3AuSGlnaFdvcmQoKSA/IExvd1dvcmQoKSA8PSBvcC5M
b3dXb3JkKCkgOiAoaTQpIEhpZ2hXb3JkKCkgPD0gKGk0KSBvcC5IaWdoV29yZCgpKTsKfQoKYm9v
bCBMb25nSW50OjpvcGVyYXRvcj4gKExvbmdJbnQgb3ApCnsKICAgIHJldHVybiAoSGlnaFdvcmQo
KSA9PSBvcC5IaWdoV29yZCgpID8gTG93V29yZCgpID4gb3AuTG93V29yZCgpIDogKGk0KSBIaWdo
V29yZCgpID4gKGk0KSBvcC5IaWdoV29yZCgpKTsKfQoKYm9vbCBMb25nSW50OjpvcGVyYXRvcj49
IChMb25nSW50IG9wKQp7CiAgICByZXR1cm4gKEhpZ2hXb3JkKCkgPT0gb3AuSGlnaFdvcmQoKSA/
IExvd1dvcmQoKSA+PSBvcC5Mb3dXb3JkKCkgOiAoaTQpIEhpZ2hXb3JkKCkgPj0gKGk0KSBvcC5I
aWdoV29yZCgpKTsKfQoKCiNpZm5kZWYgVVNFX1dPUktBUk9VTkQKCmRvdWJsZSBVTG9uZ0ludDo6
RG91YmxlKCkKewogICAgZG91YmxlIHZhbCA9IDAuMCwKICAgICAgICAgICBtdWx0aXBsaWVyID0g
MS4wOwogICAgVUxvbmdJbnQgbnVtID0gKnRoaXM7CgogICAgd2hpbGUgKG51bSA+IDApCiAgICB7
CiAgICAgICAgdmFsICs9IChtdWx0aXBsaWVyICogKG51bSAlIDEwKS5Mb3dXb3JkKCkpOwogICAg
ICAgIG51bSAvPSAxMDsKICAgICAgICBtdWx0aXBsaWVyICo9IDEwLjA7CiAgICAgICAgLy9wcmlu
dGYoIiVlXG4iLCB2YWwpOwogICAgfQoKICAgIHByaW50ZigiUkVUVVJOSU5HICVseFxuIiwgdmFs
KTsKICAgIHJldHVybiB2YWw7Cn0KCiNlbmRpZgoKCmRvdWJsZSBMb25nSW50OjpEb3VibGUoKQp7
CiAgICBkb3VibGUgdmFsOwogICAgVUxvbmdJbnQgbnVtOwoKICAgIGlmICgqdGhpcyA8IDApCiAg
ICB7CiAgICAgICAgbnVtID0gLSgqdGhpcyk7CiAgICAgICAgdmFsID0gLW51bS5Eb3VibGUoKTsK
ICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBudW0gPSAqdGhpczsKICAgICAgICB2YWwgPSBu
dW0uRG91YmxlKCk7CiAgICB9CgogICAgcHJpbnRmKCJSRVRVUk5FRCAgJWx4XG4iLCB2YWwpOwog
ICAgcmV0dXJuIHZhbDsKfQoKCgppbnQgbWFpbigpIHsKICAgIGRvdWJsZSBkOwogICAgTG9uZ0lu
dCBhKDAsIDIxNDc0ODM0NTUpOwoKICAgIGQgPSBhLkRvdWJsZSgpOwoKICAgIGlmIChkID09IDB4
N2ZmZmZmM2YpIHsKICAgICAgICBwcmludGYoIk9LXG4iKTsKICAgIH0gZWxzZSB7CiAgICAgICAg
cHJpbnRmKCJFUlJPUiAlZVxuIiwgZCk7CiAgICB9CiAgICByZXR1cm4gMDsKfQoKCg==