Add base128 encoding library.

Add base128 encoding library.

This will be used to safely encode datastore Key string ids, which are
supposedly UTF8 encoded. This base128 implementation only ever uses the lower 7
bits, and so should always roundtrip through UTF8 without any drama.

This is also designed to retain sort-order between sorted and unsorted forms
(that is: the data encoded and unencoded should memcmp sort the same way).
Unfortunately other schemes (such as base64/ascii85) don't preserve this
property.

R=dnj@chromium.org, vadimsh@chromium.org
BUG=669308
Committed: https://github.com/luci/luci-go/commit/dd65e8b8494aedf0eafff0ac6894a0c99e0a62ba

[dnj, 2016-11-29 02:03:14]

looks mostly good, comments.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128.go
File common/data/base128/base128.go (right):

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:31: if cap(dst) < ret {
I think capacity is misleading, and can lead to invisible bugs. The user should
know how much space they are going to need and allocate it up-front.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:35: whichByte := 0
nit: Just make this a uint, and cycle 1..7 instead of 0..6?

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:42: bufByte = 0
Instead of using modulus below, just reset whichbyte to 0 here. If you go with
above comment, you can fall through to next comment.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:44: whichByte = (whichByte + 1) % 7
whichByte += 1

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:60: if cap(dst) < dLen {
Same RE cap, uint comments, etc.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:82: dst := make([]byte, DecodedLen(len(src)))
Doing "DecodedLen" calculation twice here. Fall through to trusted internal
function?

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:83: _, err := Decode(dst, src)
nit: if _, err := ...; err != nil {}

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:92: ret := (encLen / 8) * 7
Consider:
func DecodedLen(v int) int {
	return (v * 7 / 8)
}

https://play.golang.org/p/Rvzw8TGvyL

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:101: pre := ((dataLen * 8) - 1)
Consider:
func EncodedLen(v int) int {
	return (((v*8) + 6) / 7)
}

https://play.golang.org/p/Rvzw8TGvyL

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:110: dst := make([]byte, EncodedLen(len(src)))
nit: you're calculating EncodedLen twice in EncodeToString. Maybe have an
internal function that trusts this?

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
File common/data/base128/base128_test.go (right):

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128_test.go:28: {9, 11},
It's a conspiracy!

[iannucci, 2016-11-29 02:14:45]

The CQ bit was checked by iannucci@chromium.org

[commit-bot: I haz the power, 2016-11-29 02:14:49]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-29 02:14:49]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-29 02:14:50]

No L-G-T-M from a valid reviewer yet. 
CQ run can only be started by full committers or once the patch has
received an L-G-T-M from a full committer.
Even if an L-G-T-M may have been provided, it was from a non-committer,
_not_ a full super star committer.
Committers are members of the group "project-infra-committers".
Note that this has nothing to do with OWNERS files.

[iannucci, 2016-11-29 02:14:55]

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128.go
File common/data/base128/base128.go (right):

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:31: if cap(dst) < ret {
On 2016/11/29 02:03:13, dnj wrote:
> I think capacity is misleading, and can lead to invisible bugs. The user
should
> know how much space they are going to need and allocate it up-front.

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:35: whichByte := 0
On 2016/11/29 02:03:13, dnj wrote:
> nit: Just make this a uint, and cycle 1..7 instead of 0..6?

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:42: bufByte = 0
On 2016/11/29 02:03:13, dnj wrote:
> Instead of using modulus below, just reset whichbyte to 0 here. If you go with
> above comment, you can fall through to next comment.

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:44: whichByte = (whichByte + 1) % 7
On 2016/11/29 02:03:13, dnj wrote:
> whichByte += 1

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:60: if cap(dst) < dLen {
On 2016/11/29 02:03:13, dnj wrote:
> Same RE cap, uint comments, etc.

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:82: dst := make([]byte, DecodedLen(len(src)))
On 2016/11/29 02:03:13, dnj wrote:
> Doing "DecodedLen" calculation twice here. Fall through to trusted internal
> function?

meh

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:83: _, err := Decode(dst, src)
On 2016/11/29 02:03:13, dnj wrote:
> nit: if _, err := ...; err != nil {}

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:92: ret := (encLen / 8) * 7
On 2016/11/29 02:03:13, dnj wrote:
> Consider:
> func DecodedLen(v int) int {
> 	return (v * 7 / 8)
> }
> 
> https://play.golang.org/p/Rvzw8TGvyL

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:101: pre := ((dataLen * 8) - 1)
On 2016/11/29 02:03:13, dnj wrote:
> Consider:
> func EncodedLen(v int) int {
> 	return (((v*8) + 6) / 7)
> }
> 
> https://play.golang.org/p/Rvzw8TGvyL

Done.

https://codereview.chromium.org/2538553003/diff/1/common/data/base128/base128...
common/data/base128/base128.go:110: dst := make([]byte, EncodedLen(len(src)))
On 2016/11/29 02:03:13, dnj wrote:
> nit: you're calculating EncodedLen twice in EncodeToString. Maybe have an
> internal function that trusts this?

meh

[dnj, 2016-11-29 02:16:10]

lgtm

[iannucci, 2016-11-29 02:16:19]

The CQ bit was checked by iannucci@chromium.org

[commit-bot: I haz the power, 2016-11-29 02:16:27]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-29 02:23:25]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1480385779966950,
"parent_rev": "3e06bc063f33ca9ade827be12b3121f4aa28ba6b", "commit_rev":
"dd65e8b8494aedf0eafff0ac6894a0c99e0a62ba"}

[commit-bot: I haz the power, 2016-11-29 02:23:27]

Description was changed from

==========
Add base128 encoding library.

This will be used to safely encode datastore Key string ids, which are
supposedly UTF8 encoded. This base128 implementation only ever uses the lower 7
bits, and so should always roundtrip through UTF8 without any drama.

This is also designed to retain sort-order between sorted and unsorted forms
(that is: the data encoded and unencoded should memcmp sort the same way).
Unfortunately other schemes (such as base64/ascii85) don't preserve this
property.

R=dnj@chromium.org, vadimsh@chromium.org
BUG=669308
==========

to

==========
Add base128 encoding library.

This will be used to safely encode datastore Key string ids, which are
supposedly UTF8 encoded. This base128 implementation only ever uses the lower 7
bits, and so should always roundtrip through UTF8 without any drama.

This is also designed to retain sort-order between sorted and unsorted forms
(that is: the data encoded and unencoded should memcmp sort the same way).
Unfortunately other schemes (such as base64/ascii85) don't preserve this
property.

R=dnj@chromium.org, vadimsh@chromium.org
BUG=669308

Committed:
https://github.com/luci/luci-go/commit/dd65e8b8494aedf0eafff0ac6894a0c99e0a62ba
==========

[commit-bot: I haz the power, 2016-11-29 02:23:28]

Committed patchset #2 (id:20001) as
https://github.com/luci/luci-go/commit/dd65e8b8494aedf0eafff0ac6894a0c99e0a62ba