[Courgette] Add third party-library: libdivsufsort.

[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=631482, 608885
Committed: https://crrev.com/d63dcb01c3a8fc30a840ce5aaab8ea5e6c9107e4
Cr-Commit-Position: refs/heads/master@{#408141}

[huangs, 2016-07-18 15:52:39]

For divsufsort: Here are matches from original source
(https://github.com/y-256/libdivsufsort) to our adaptation:

lib\divsufsort.c <==> divsufsort.cc
lib\sssort.c <==> sssort.cc
lib\trsort.c <==> trsort.cc
include\divsufsort_private.h <==> divsufsort_private.h (sssort.cc & trsort.cc
has macros)
include\divsufsort.h.cmake <==> divsufsort.h

[huangs, 2016-07-18 18:33:17]

Description was changed from

==========
[Courgette] Replace QSufSort with libdivsufsort

This CL adds and uses third-party library libdivsufsort in Courgette.
Source: https://github.com/y-256/libdivsufsort

Benefits of replacing QSufSort with libdivsufsort are:
- Faster patch generation (time reduced by 20% to 25%).
- Reduced memory usage (by about 40%).

Drawback: courgette.exe and courgette64.exe size are increased by ~7%,
or about 34.3 kB and 43.5 kB.

BUG=608885
==========

to

==========
[Courgette] Add third-party library: libdivsufsort

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=608885
==========

[huangs, 2016-07-18 18:33:17]

huangs@chromium.org changed reviewers:
+ chrisha@chromium.org

[huangs, 2016-07-18 18:33:40]

Reduced CL scope to add-only.  PTAL.

[chrisha, 2016-07-19 21:05:18]

Great, lgtm!

https://codereview.chromium.org/2156223002/diff/20001/courgette/third_party/d...
File courgette/third_party/divsufsort/README.chromium (right):

https://codereview.chromium.org/2156223002/diff/20001/courgette/third_party/d...
courgette/third_party/divsufsort/README.chromium:13: The copy on this directory
is so extensively modified that the binary format is
in* this

[huangs, 2016-07-19 21:44:30]

huangs@chromium.org changed reviewers:
+ wfh@chromium.org

[huangs, 2016-07-19 21:44:31]

Adding wfh@ to review, PTAL. Thanks!

https://codereview.chromium.org/2156223002/diff/20001/courgette/third_party/d...
File courgette/third_party/divsufsort/README.chromium (right):

https://codereview.chromium.org/2156223002/diff/20001/courgette/third_party/d...
courgette/third_party/divsufsort/README.chromium:13: The copy on this directory
is so extensively modified that the binary format is
On 2016/07/19 21:05:18, chrisha (slow) wrote:
> in* this

Done.

[Will Harris, 2016-07-19 21:46:02]

this will need an l-g-t-m from third party reviewers (for license etc)

[huangs, 2016-07-19 22:18:18]

The review go/courgette-use-libdivsufsort has been approved; please see email
thread "Eng Review Request: Using libdivsufsort in Courgette".  Or do you mean
something more detailed?

[Will Harris, 2016-07-20 19:30:57]

lgtm

[huangs, 2016-07-20 21:06:12]

Thanks.  Committing!

[huangs, 2016-07-20 21:06:22]

Description was changed from

==========
[Courgette] Add third-party library: libdivsufsort

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=608885
==========

to

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=608885
==========

[huangs, 2016-07-20 21:06:36]

The CQ bit was checked by huangs@chromium.org

[huangs, 2016-07-20 21:06:36]

The patchset sent to the CQ was uploaded after l-g-t-m from
chrisha@chromium.org, wfh@chromium.org
Link to the patchset: https://codereview.chromium.org/2156223002/#ps60001
(title: "Update ChangeLog dates.")

[commit-bot: I haz the power, 2016-07-20 21:07:02]

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-07-20 22:48:47]

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

[commit-bot: I haz the power, 2016-07-20 22:48:48]

Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[huangs, 2016-07-22 00:14:45]

huangs@chromium.org changed reviewers:
+ phajdan.jr@chromium.org

[huangs, 2016-07-22 00:14:46]

+phajdan.jr@ for checklicenses.py, PTAL. Thanks!

[huangs, 2016-07-22 00:14:53]

The CQ bit was checked by huangs@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-22 00:15:17]

Dry run: 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-07-22 02:17:43]

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

[commit-bot: I haz the power, 2016-07-22 02:17:45]

Dry run: Try jobs failed on following builders:
  android_arm64_dbg_recipe on master.tryserver.chromium.android (JOB_TIMED_OUT,
no build URL)

[Paweł Hajdan Jr., 2016-07-22 13:23:52]

https://codereview.chromium.org/2156223002/diff/80001/tools/checklicenses/che...
File tools/checklicenses/checklicenses.py (right):

https://codereview.chromium.org/2156223002/diff/80001/tools/checklicenses/che...
tools/checklicenses/checklicenses.py:642: 'courgette/third_party/divsufsort': [ 
# http://crbug.com/608885
No, this needs to be *upstream* bug report about missing license headers.

Since I'll be taking vacation next week, feel free to ask e.g. thestig@ to
finish the review.

[huangs, 2016-07-26 15:00:11]

Description was changed from

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=608885
==========

to

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=631482,608885
==========

[huangs, 2016-07-26 15:00:11]

huangs@chromium.org changed reviewers:
+ thestig@chromium.org
- phajdan.jr@chromium.org

[huangs, 2016-07-26 15:07:11]

Filed upstream bug http://crbug.com/631482 and added to BUG list.

Request review from thestig@, PTAL.  Thanks!

[Lei Zhang, 2016-07-26 17:38:11]

https://chromiumcodereview.appspot.com/2156223002/diff/80001/courgette/third_...
File courgette/third_party/divsufsort/README.chromium (right):

https://chromiumcodereview.appspot.com/2156223002/diff/80001/courgette/third_...
courgette/third_party/divsufsort/README.chromium:5: License File: LICENCE
Security Critical: [yes/no] ?

https://chromiumcodereview.appspot.com/2156223002/diff/80001/courgette/third_...
courgette/third_party/divsufsort/README.chromium:13: The copy in this directory
is so extensively modified that the binary format is
Given the extensive changes, do you want to just add the licenses to all the
files to pass the license check?

See third_party/wayland/src/tests/headers-protocol-test.c as an example of a
file with the same MIT license.

https://chromiumcodereview.appspot.com/2156223002/diff/80001/tools/checklicen...
File tools/checklicenses/checklicenses.py (right):

https://chromiumcodereview.appspot.com/2156223002/diff/80001/tools/checklicen...
tools/checklicenses/checklicenses.py:642: 'courgette/third_party/divsufsort': [ 
# http://crbug.com/608885
631482

[huangs, 2016-07-26 20:24:19]

Updated re. licenses, PTAL.

https://codereview.chromium.org/2156223002/diff/80001/courgette/third_party/d...
File courgette/third_party/divsufsort/README.chromium (right):

https://codereview.chromium.org/2156223002/diff/80001/courgette/third_party/d...
courgette/third_party/divsufsort/README.chromium:13: The copy in this directory
is so extensively modified that the binary format is
Per discussion in http://crbug.com/631482, my mistake was to defer the
boilerplate to LICENSE file. Putting back the boilerplate the files (this also
fixes checklicenses.py)

https://codereview.chromium.org/2156223002/diff/80001/tools/checklicenses/che...
File tools/checklicenses/checklicenses.py (right):

https://codereview.chromium.org/2156223002/diff/80001/tools/checklicenses/che...
tools/checklicenses/checklicenses.py:642: 'courgette/third_party/divsufsort': [ 
# http://crbug.com/608885
Can remove this now that we put back license boilerplate in front of
libdivsufsort files.

[Lei Zhang, 2016-07-26 20:43:14]

Thanks, you don't need my approval here anymore.

[huangs, 2016-07-26 20:47:55]

Okay, I'll take that as LG™.  Thanks, and committing!

[huangs, 2016-07-26 21:08:34]

The CQ bit was checked by huangs@chromium.org

[huangs, 2016-07-26 21:08:34]

The patchset sent to the CQ was uploaded after l-g-t-m from
chrisha@chromium.org, wfh@chromium.org
Link to the patchset: https://codereview.chromium.org/2156223002/#ps120001
(title: "Small LICENSE update; remove debugging code in checklicenses.py.")

[commit-bot: I haz the power, 2016-07-26 21:09:20]

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-07-26 23:18:45]

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

[commit-bot: I haz the power, 2016-07-26 23:18:46]

Try jobs failed on following builders:
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)

[huangs, 2016-07-27 15:18:08]

The CQ bit was checked by huangs@chromium.org

[huangs, 2016-07-27 15:18:08]

The patchset sent to the CQ was uploaded after l-g-t-m from
chrisha@chromium.org, wfh@chromium.org
Link to the patchset: https://codereview.chromium.org/2156223002/#ps140001
(title: "Fix typo in README.chromium: LICEN*S*E.")

[commit-bot: I haz the power, 2016-07-27 15:18:32]

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-07-27 16:08:13]

Description was changed from

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=631482,608885
==========

to

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=631482,608885
==========

[commit-bot: I haz the power, 2016-07-27 16:08:15]

Committed patchset #8 (id:140001)

[commit-bot: I haz the power, 2016-07-27 16:09:54]

Description was changed from

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=631482,608885
==========

to

==========
[Courgette] Add third-party library: libdivsufsort.

We wish to use third-party library libdivsufsort in Courgette to replace
QSufSort in Courgette-gen. This will reduce time and memory usage. This
CL focuses on adding libdivsufsort and tests. We will make the switch in
a follow-up CL.

Proposal: go/courgette-use-libdivsufsort
Code source: https://github.com/y-256/libdivsufsort

BUG=631482,608885

Committed: https://crrev.com/d63dcb01c3a8fc30a840ce5aaab8ea5e6c9107e4
Cr-Commit-Position: refs/heads/master@{#408141}
==========

[commit-bot: I haz the power, 2016-07-27 16:09:56]

Patchset 8 (id:??) landed as
https://crrev.com/d63dcb01c3a8fc30a840ce5aaab8ea5e6c9107e4
Cr-Commit-Position: refs/heads/master@{#408141}