The current implementation of the extended Euclidean GCD algorithm
calculates both cosequences x and y inside the division loop. This
is unneccessary since the second Bezout coefficient can be obtained
at the end of calculation via a multiplication, subtraction and a
division.  In case only one coefficient is needed, e.g. ModInverse
this calculation can be skipped entirely.  This is a standard
optimization, see e.g.

"Handbook of Elliptic and Hyperelliptic Curve Cryptography"
Cohen et al pp 191
Available at:
http://cs.ucsb.edu/~koc/ccs130h/2013/EllipticHyperelliptic-CohenFrey.pdf

Updates #15833

Change-Id: I1e0d2e63567cfed97fd955048fe6373d36f22757
Reviewed-on: https://go-review.googlesource.com/50530Reviewed-by: Robert Griesemer <gri@golang.org>

The current implementation uses a shift and add
loop to compute the product of x's exponent xe and
the integer part of y (yi) for yi up to 1<<63.
Since xe is an 11-bit exponent, this product can be
up to 74-bits and overflow both 32 and 64-bit int.

This change checks whether the accumulated exponent
will fit in the 11-bit float exponent of the output
and breaks out of the loop early if overflow is detected.

The current handling of yi >= 1<<63 uses Exp(y * Log(x))
which incorrectly returns Nan for x<0.  In addition,
for y this large, Exp(y * Log(x)) can be enumerated
to only overflow except when x == -1 since the
boundary cases computed exactly:

Pow(NextAfter(1.0, Inf(1)), 1<<63)  == 2.72332... * 10^889
Pow(NextAfter(1.0, Inf(-1)), 1<<63) == 1.91624... * 10^-445

exceed the range of float64. So, the call can be
replaced with a simple case statement analgous to
y == Inf that correctly handles x < 0 as well.

Fixes #7394

Change-Id: I6f50dc951f3693697f9669697599860604323102
Reviewed-on: https://go-review.googlesource.com/48290Reviewed-by: Robert Griesemer <gri@golang.org>

Change-Id: Ie5d12ba4105fec17551637d066d0dffd508f74a4
Reviewed-on: https://go-review.googlesource.com/55261
Run-TryBot: Alex Brainman <alex.brainman@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

Change-Id: Iee9db172d28d4d372fa617907078a494e764bf12
Reviewed-on: https://go-review.googlesource.com/55260Reviewed-by: Ian Lance Taylor <iant@golang.org>

Change-Id: I4d4e8452b9b9e628f3ea8b2b727ad63ec2a1dd31
Reviewed-on: https://go-review.googlesource.com/55259Reviewed-by: Ian Lance Taylor <iant@golang.org>

Change-Id: Id3aeeaeaacf5f079fb2ddad579f2f209b7fc0e06
Reviewed-on: https://go-review.googlesource.com/55258Reviewed-by: Ian Lance Taylor <iant@golang.org>

Change-Id: Icd13b32d35cde474c9292227471f916a64af88eb
Reviewed-on: https://go-review.googlesource.com/55257Reviewed-by: Ian Lance Taylor <iant@golang.org>

The Writer logic was not consistent about when an IO error would
persist across multiple calls on Writer's methods.

Thus, to make the error handling more consistent we always check
the persistent state of the error prior to every exported method
call, and return an error if set. Otherwise, it is the responsibility
of every exported method to persist any fatal errors that may occur.

As a simplification, we can remove the close field since that
information can be represented by simply storing ErrWriteAfterClose
in the err field.

Change-Id: I8746ca36b3739803e0373253450db69b3bd12f38
Reviewed-on: https://go-review.googlesource.com/55590
Run-TryBot: Joe Tsai <joetsai@digital-static.net>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

The GNU tar format defines the following type flags:
	TypeGNULongName = 'L' // Next file has a long name
	TypeGNULongLink = 'K' // Next file symlinks to a file w/ a long name

Anytime a string exceeds the field dedicated to store it, the GNU format
permits a fake "file" to be prepended where that file entry has a Typeflag
of 'L' or 'K' and the contents of the file is a NUL-terminated string.

Contrary to previous TODO comments,
the GNU format supports arbitrary strings (without NUL) rather UTF-8 strings.
The manual says the following:
<<<
The name, linkname, magic, uname, and gname are
null-terminated character strings

> <<<
> All characters in header blocks are represented
> by using 8-bit characters in the local variant of ASCII.


From this description, we gather the following:
* We must forbid NULs in any GNU strings
* Any 8-bit value (other than NUL) is permitted

Since the modern world has moved to UTF-8, it is really difficult to
determine what a "local variant of ASCII" means. For this reason,
we treat strings as just an arbitrary binary string (without NUL)
and leave it to the user to determine the encoding of this string.
(Practically, it seems that UTF-8 is the typical encoding used
in GNU archives seen in the wild).

The implementation of GNU tar seems to confirm this interpretation
of the manual where it permits any arbitrary binary string to exist
within these fields so long as they do not contain the NUL character.

 $ touch `echo -e "not\x80\x81\x82\x83utf8"`
 $ gnutar -H gnu --tar -cvf gnu-not-utf8.tar $(echo -e "not\x80\x81\x82\x83utf8")

The fact that we permit arbitrary binary in GNU strings goes
hand-in-hand with the fact that GNU also permits a "base-256" encoding
of numeric fields, which is effectively two-complement binary.

Change-Id: Ic037ec6bed306d07d1312f0058594bd9b64d9880
Reviewed-on: https://go-review.googlesource.com/55573Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

In the existing implementation, if pattern is an empty string,
program calls a panic with the message which is a concatenation of
"http: invalid pattern " and pattern.
In this case, pattern is an empty, so the commit removes
this concatenation and the trailing space.

Fixes: #21102

Change-Id: I49f58b52d835311a6ac642de871eb15646e48a54
Reviewed-on: https://go-review.googlesource.com/50350Reviewed-by: Dmitri Shuralyov <shurcool@gmail.com>
Reviewed-by: Tom Bergan <tombergan@google.com>
Run-TryBot: Tom Bergan <tombergan@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

The code was adding race.Errors to t.raceErrors before checking
Failed, but Failed was using t.raceErrors+race.Errors. We don't want
to change Failed, since that would affect tests themselves, so modify
the harness to not unnecessarily change t.raceErrors.

Updates #19851
Fixes #21338
Change-Id: I7bfdf281f90e045146c92444f1370d55c45221d4
Reviewed-on: https://go-review.googlesource.com/54050Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

This reduces the code footprint of code like:

println("foo=", foo, "bar=", bar)

which is fairly common in the runtime.

Prior to this change, this makes function calls to print each of:

"foo=", " ", foo, " ", "bar=", " ", bar, "\n"

After this change, this prints:

"foo= ", foo, " bar= ", bar, "\n"

This shrinks the hello world binary by 0.4%.
More importantly, this improves the instruction
density of important runtime routines.

Change-Id: I8971bdf5382fbaaf4a82bad4442f9da07c28d395
Reviewed-on: https://go-review.googlesource.com/55098
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

Rather than emitting spaces and newlines for println
as we walk the expression, construct it all up front.
This enables further optimizations.

This requires using printstring instead of print in
the implementation of printsp and printnl,
on pain of infinite recursion.
That's ok; it's more efficient anyway, and just as simple.
While we're here, do it for other print routines as well.

Change-Id: I61d7df143810e00710c4d4d948d904007a7fd190
Reviewed-on: https://go-review.googlesource.com/55097
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

Passes toolstash-check.

Change-Id: I6386a37a35221de8d3944253beee668927810f17
Reviewed-on: https://go-review.googlesource.com/55096
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

Superficial simplifications: reduce variable scope,
eliminate pointless temporaries, use a switch statement.

Passes toolstash-check.

Change-Id: I6450493a0583a6ce8ec0461b66954cf1445a754f
Reviewed-on: https://go-review.googlesource.com/55095
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Marvin Stenger <marvin.stenger94@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

This effectively reverts

https://golang.org/cl/53770

and adds a guide on what not to add in this file.

Update #21458

Change-Id: I7c740d492b70628b5d9f9e1622014995a3f6f8ec
Reviewed-on: https://go-review.googlesource.com/55871Reviewed-by: Ian Lance Taylor <iant@golang.org>

Writing to selectdone on the stack of another goroutine meant a
pretty subtle dance between the select code and the stack copying
code. Instead move the selectdone variable into the g struct.

Change-Id: Id246aaf18077c625adef7ca2d62794afef1bdd1b
Reviewed-on: https://go-review.googlesource.com/53390Reviewed-by: Austin Clements <austin@google.com>
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

I noticed that we don't set an itab's function pointers at compile
time. Instead, we currently do it at executable startup.

Set the function pointers at compile time instead. This shortens
startup time. It has no effect on normal binary size. Object files
will have more relocations, but that isn't a big deal.

For PIE there are additional pointers that will need to be adjusted at
load time. There are already other pointers in an itab that need to be
adjusted, so the cache line will already be paged in. There might be
some binary size overhead to mark these pointers. The "go test -c
-buildmode=pie net/http" binary is 0.18% bigger.

Update #20505

Change-Id: I267c82489915b509ff66e512fc7319b2dd79b8f7
Reviewed-on: https://go-review.googlesource.com/44341
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>

Currently, GC captures the start-the-world time stamp after
startTheWorldWithSema returns. This is problematic for two reasons:

1. It's possible to get preempted between startTheWorldWithSema
starting the world and calling nanotime.

2. startTheWorldWithSema does several clean-up tasks after the world
is up and running that on rare occasions can take upwards of 10ms.

Since the runtime uses the start-the-world time stamp to compute the
STW duration, both of these can significantly inflate the reported STW
duration.

Fix this by having startTheWorldWithSema itself call nanotime once the
world is started.

Change-Id: I114630234fb73c9dabae50a2ef1884661f2459db
Reviewed-on: https://go-review.googlesource.com/55410
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Rick Hudson <rlh@golang.org>

Fixes #20488

Change-Id: Iae963b612aea3d9e814b08f655e2eb019ece256e
Reviewed-on: https://go-review.googlesource.com/44110Reviewed-by: Adam Langley <agl@golang.org>
Run-TryBot: Adam Langley <agl@golang.org>

Detected by BoGo test FragmentAcrossChangeCipherSpec-Server-Packed.

Change-Id: I9a76697b9cdeb010642766041971de5c7e533481
Reviewed-on: https://go-review.googlesource.com/48811Reviewed-by: Adam Langley <agl@golang.org>
Run-TryBot: Adam Langley <agl@golang.org>

Change-Id: I77d9c77875519d77bac49cc8870c2e0c4563fe55
Reviewed-on: https://go-review.googlesource.com/44313Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Adam Langley <agl@golang.org>
Run-TryBot: Adam Langley <agl@golang.org>

name                                       time/op
HandshakeServer/RSA-4                      1.10ms ± 0%
HandshakeServer/ECDHE-P256-RSA-4           1.23ms ± 1%
HandshakeServer/ECDHE-P256-ECDSA-P256-4     178µs ± 1%
HandshakeServer/ECDHE-X25519-ECDSA-P256-4   180µs ± 2%
HandshakeServer/ECDHE-P521-ECDSA-P521-4    19.8ms ± 1%

Change-Id: I6b2c79392995d259cfdfc5199be44cc7cc40e155
Reviewed-on: https://go-review.googlesource.com/44730Reviewed-by: Adam Langley <agl@golang.org>
Run-TryBot: Adam Langley <agl@golang.org>

The processClientKeyExchange and processServerKeyExchange functions unmarshal an
encoded EC point and explicitly check whether the point is on the curve. The explicit
check can be omitted because elliptic.Unmarshal fails if the point is not on the curve
and the returned error would always be the same.

Fixes #20496

Change-Id: I5231a655eace79acee2737dd036a0c255ed42dbb
Reviewed-on: https://go-review.googlesource.com/44311Reviewed-by: Adam Langley <agl@golang.org>
Reviewed-by: Avelino <t@avelino.xxx>
Run-TryBot: Adam Langley <agl@golang.org>

asn1.NullRawValue was used according to RFC 3279 2.2.1. Without this tag,
the output didn't match openssl.

Fixes #19972

Change-Id: Ia52ddb810888837f913dbd65c4e1328f6c8084bb
Reviewed-on: https://go-review.googlesource.com/40730Reviewed-by: Adam Langley <agl@golang.org>
Run-TryBot: Adam Langley <agl@golang.org>
Run-TryBot: Emmanuel Odeke <emm.odeke@gmail.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>

Change-Id: I1b42fca2107b06e6fc95728f7bf3d08d005c4cb4
Reviewed-on: https://go-review.googlesource.com/55810Reviewed-by: Ian Lance Taylor <iant@golang.org>

golang.org/cl/55130 added utimensat for Solaris but didn't use it in
UtimesNano (despite indicating otherwise in the commit message). Fix
this by also using utimensat for UtimesNano on Solaris.

Because all versions of Solaris suppported by Go support utimensat,
there is no need for the fallback logic and utimensat can be called
unconditionally.

This issue was pointed out by Shawn Walker-Salas.

Updates #16480

Change-Id: I114338113a6da3cfcb8bca950674bdc8f5a7a9e5
Reviewed-on: https://go-review.googlesource.com/55141
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

Some IDEs (e.g. intellij IDE based ones) create the .idea folder
to store project specific settings. This is irrelevant to Go project
that does not assume any specific IDEs, but interferes with git.

Change-Id: I0c93d9a3f7edff095fbe0c7a53b06c92b391c970
Reviewed-on: https://go-review.googlesource.com/53770Reviewed-by: Ian Lance Taylor <iant@golang.org>

The destination slice does not need to be created at all. The source
slice itself can be used as the destination because the decode loop
increments by one and then the 'seen' byte is not used anymore. Therefore
the decoded byte can be stored in that index of the source slice itself.

This trick cannot be applied to EncodeString() because in that case,
the destination slice is large than the source. And for a single byte
in the source slice, two bytes in the destination slice is written.

func BenchmarkDecodeString(b *testing.B) {
  for i := 0; i < b.N; i++ {
    DecodeString("0123456789abcdef")
  }
}

name          old time/op    new time/op    delta
DecodeString    71.0ns ± 6%    58.0ns ± 0%  -18.28%  (p=0.008 n=5+5)

name          old alloc/op   new alloc/op   delta
DecodeString     16.0B ± 0%      8.0B ± 0%  -50.00%  (p=0.008 n=5+5)

name          old allocs/op  new allocs/op  delta
DecodeString      1.00 ± 0%      1.00 ± 0%     ~     (all equal)

Change-Id: Id98db4e712444557a804155457a4dd8d1b8b416d
Reviewed-on: https://go-review.googlesource.com/55611Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

CL golang.org/cl/55130 messed up the definition of _AT_FDCWD on
dragonfly.

This fixes the following test failure on dragonfly/amd64:

  --- FAIL: TestPackageMainTestImportsArchiveNotBinary (0.00s)
  	  go_test.go:192: chtimes ./testdata/src/main_test/m.go: bad file descriptor

Change-Id: I4c96983769e6b02d714859dc838875c3c0f1be50
Reviewed-on: https://go-review.googlesource.com/55690
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

The stxr/stxrw/stxrb/stxrh instructions belong to STLXR-like instructions
set and they require special handling. The current code has no special
handling for those instructions.

The fix adds the special handling for those instructions.

Uncomment stxr/stxrw/stxrb/stxrh test cases.

Fixes #21397
Change-Id: I31cee29dd6b30b1c25badd5c7574dda7a01bf016
Reviewed-on: https://go-review.googlesource.com/54951
Run-TryBot: Cherry Zhang <cherryyz@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

Improve static branch prediction in arm64 wrapper prologue
by making the unusual case branch forwards. (Most other
architectures implement this optimization.)

Additionally, replace a CMP+BNE pair with a CBNZ
to save one instruction.

Change-Id: Id970038b34b4aaec18c101d62e2ee00f3e32a761
Reviewed-on: https://go-review.googlesource.com/54070
Run-TryBot: Cherry Zhang <cherryyz@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

Otherwise, some test flags don't work.

Change-Id: Iacf3930d0eec28e4d690cd382adbb2ecf866a0e2
Reviewed-on: https://go-review.googlesource.com/55615Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Add support for generating TBZ/TBNZ instructions.

The bit-test-and-branch pattern shows up in a number of
important places, including the runtime (gc bitmaps).

Before this change, there were 3 TB[N]?Z instructions in the Go tool,
all of which were in hand-written assembly. After this change, there
are 285. Also, the go1 benchmark binary gets about 4.5kB smaller.

Fixes #21361

Change-Id: I170c138b852754b9b8df149966ca5e62e6dfa771
Reviewed-on: https://go-review.googlesource.com/54470
Run-TryBot: Philip Hofer <phofer@umich.edu>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

TestSizes has been added in CL 55551. This test is
failing on Plan 9 because executables don't have
a DWARF symbol table.

Fixes #21453.

Change-Id: I560611b49aea5417e8c5ac0cec6c7882bd9f8335
Reviewed-on: https://go-review.googlesource.com/55692
Run-TryBot: David du Colombier <0intro@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>

struct32 and struct40 structs are already declared, remove them to
make runtime tests build.

Change-Id: I3814f2b850dcb15c4002a3aa22e2a9326e5a5e53
Reviewed-on: https://go-review.googlesource.com/55614Reviewed-by: Martin Möhrmann <moehrmann@google.com>

Where possible generate calls to runtime makechan with int arguments
during compile time instead of makechan with int64 arguments.

This eliminates converting arguments for calls to makechan with
int64 arguments for platforms where int64 values do not fit into
arguments of type int.

A similar optimization for makeslice was introduced in CL
golang.org/cl/27851.

386:
name                old time/op  new time/op  delta
MakeChan/Byte       52.4ns ± 6%  45.0ns ± 1%  -14.14%  (p=0.000 n=10+10)
MakeChan/Int        54.5ns ± 1%  49.1ns ± 1%   -9.87%  (p=0.000 n=10+10)
MakeChan/Ptr         150ns ± 1%   143ns ± 0%   -4.38%  (p=0.000 n=9+7)
MakeChan/Struct/0   49.2ns ± 2%  43.2ns ± 2%  -12.27%  (p=0.000 n=10+10)
MakeChan/Struct/32  81.7ns ± 2%  76.2ns ± 1%   -6.71%  (p=0.000 n=10+10)
MakeChan/Struct/40  88.4ns ± 2%  82.5ns ± 2%   -6.60%  (p=0.000 n=10+10)

AMD64:
name                old time/op  new time/op  delta
MakeChan/Byte       83.4ns ± 8%  80.8ns ± 3%    ~     (p=0.171 n=10+10)
MakeChan/Int         101ns ± 3%   101ns ± 2%    ~     (p=0.412 n=10+10)
MakeChan/Ptr         128ns ± 1%   128ns ± 1%    ~     (p=0.191 n=10+10)
MakeChan/Struct/0   67.6ns ± 3%  68.7ns ± 4%    ~     (p=0.224 n=10+10)
MakeChan/Struct/32   138ns ± 1%   139ns ± 1%    ~     (p=0.185 n=10+9)
MakeChan/Struct/40   154ns ± 1%   154ns ± 1%  -0.55%  (p=0.027 n=10+9)

Change-Id: Ie854cb066007232c5e9f71ea7d6fe27e81a9c050
Reviewed-on: https://go-review.googlesource.com/55140
Run-TryBot: Martin Möhrmann <moehrmann@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

The logic for USTAR was disabled because a previous implementation of
Writer had a wrong understanding of the differences between USTAR and GNU,
causing the prefix field is incorrectly be populated in GNU files.

Now that this issue has been fixed, we can re-enable the logic for USTAR
path splitting, which allows Writer to use the USTAR for a wider range
of possible inputs.

Updates #9683
Updates #12594
Updates #17630

Change-Id: I9fe34e5df63f99c6dd56fee3a7e7e4d6ec3995c9
Reviewed-on: https://go-review.googlesource.com/55574
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

Move all sentinel errors to common.go since some of them are
returned by both the reader and writer and remove errInvalidHeader
since it not used.

Also, consistently use the "tar: " prefix for errors.

Change-Id: I0afb185bbf3db80dfd9595321603924454a4c2f9
Reviewed-on: https://go-review.googlesource.com/55650Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

Move variable declarations closer to their first uses.

Use an additional string variable s0 for error reporting that references
the original input string. This allows the variable s to be modified.

Change-Id: I4725152490ca1dc10c1161ad8ad2f4ae8933493f
Reviewed-on: https://go-review.googlesource.com/55138Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Reviewed-by: Marvin Stenger <marvin.stenger94@gmail.com>
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>