Add support for UTF-8 encoding/decoding with SIMD

Decoding from UTF-8 is easy: if the high bit is set, we fall back to
the byte-by-byte decoding. Encoding to UTF-8 requires a little bit
more work: to detect anything between 0x0080 and 0xffff, we have
several options but none as easy as above. Multiple alternatives are
in the benchmark code.

In both loops, we do two things once we run into a non-ASCII
character: first, we continue the loop for the remainder of ASCII
characters in the buffer (which we can tell by checking the bits set
in the mask), then we find the last non-ASCII character in that
16-character group, so we don't reenter the SSE code too soon.

For the UTF-8 encoding, I have chosen the alternative that results in
the best performance. It's closely tied to the alternative running the
PMIN instruction, but that requires SSE 4.1. It's not worth the
complexity. And quite counter-intuitively, the dedicated string
instruction from SSE 4.2 performs most poorly of all solutions. This
begs re-visiting the performance of the toLatin1 encoder.

The best of 10 benchmark runs of this code were measured on my
SandyBridge CPU @ 2.66 GHz (turbo @ 3.3 GHz), both as CPU cycles and
as CPU ticks:

  Compared to:        ICU             Qt 4.7      non-SSE Qt 5.3
  Data set     fromUtf8  toUtf8  fromUtf8 toUtf8  fromUtf8 toUtf8
 ASCII only      7.50x    6.22x    6.94x   7.60x    4.45x   4.90x
2-char UTF-8     1.17x    1.33x    1.64x   1.56x    1.01x   1.02x
3-char UTF-8     1.08x    1.18x    1.48x   1.33x    0.97x   0.92x
4-char UTF-8     1.05x    1.19x    1.20x   1.21x    0.97x   0.97x
Creator data     3.62x    2.16x    2.60x   1.25x    1.78x   1.23x

As shown by the numbers, the SSE-based code is slightly worse than the
non-SSE code for dense non-ASCII strings. However, as evident in the
Qt Creator data, most strings manipulated by applications are either
pure ASCII or mostly so, so there's a net gain.

Done-with: H. Peter Anvin <hpa@linux.intel.com>
Change-Id: Ia74fbdfdcd7b088f6cba5048c03a153c01f5dbc1
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Improve ucstrncmp with SSE2

The benchmarks showed that the basic SSE2-based building block
improves performance by about 50% with data extracted from a Qt
Creator run. None of the other alternatives provide clear better
results -- the best was 3.8% and with only one compiler.

Change-Id: I77314785afecfacaf21c41fd79c97cadf357f895
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Merge qMemEquals and ucstrncmp

qMemEquals is the same as ucstrncmp and checking that the comparison
was 0, so implement it like that. Meanwhile, it already had code for
doing 32-bit comparisons in the absence of higher SIMD optimizations,
which we can now make use of.

Change-Id: If26b446856e3b756efabc98b471fcdc344a8e732
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Improve qstring.cpp:findChar with SSE2

This updates only the case-sensitive searching. The case-insensitive
part requires quite a few Unicode transformations.

The benchmarks tried are the plain word-by-word comparison used in Qt
5.2 and in builds without SSE2; the SSE2 benchmark; a benchmark using
the SSE4.2 "strchr" instruction. I've run the benchmark both for CPU
cyles used as well as bytes/sec scanning strings.

Improvement over the Qt 5.2 code:

            GCC 4.7         GCC 4.9        Clang 3.4        ICC 14
          cycles  MB/s    cycles  MB/s    cycles  MB/s    cycles  MB/s
SSE2       2.1x   2.9x     2.2x   2.9x     2.1x   3.1x     2.2x   3.1x
SSE4.2     1.5x   1.7x     1.5x   1.7x     1.5x   1.7x     1.6x   1.8x

Once again, the SSE4.2 instruction wasn't as effective as I'd hoped
(not to mention that Clang seems to have some bugs emitting it).

Change-Id: I57c6e65e91791bb5265965cbd1af7fbd8fe7f588
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Centralize the UTF16-Latin1 comparisons in one place

We have quite a few versions of this code in qstring.cpp, which means
that it's hard to optimize them all. Instead, create two functions to
do the comparisons, one case-sensitive (ucstrncmp & ucstrcmp) and one
case-insensitive (ucstricmp).

Change-Id: I55c6588ade160bc8d16e19727b8f3dca523b38bf
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Improve the QString/QLatin1String ucstrncmp with SSE2

Change-Id: I6a7ce281096bb99352132f775ae32fcaf55bd32c
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Unroll the tail loops of the SSE2-improved code

Change-Id: I1a51ceab3bdabd39bdb9dc2714debb3ad2c2380c
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Merge all conversions from Latin-1 in qstring.cpp into a single function

Amazing how many places had the conversion duplicated. When compiling
with GCC under -O3 (which enables -ftree-vectorize), GCC would use SIMD
by using the PMOVZXBW instruction, but only if the -msse4.1 was passed
(or equivalent -march= switch), which almost no one did.

Also, the two lastIndexOf and the qt_find_latin1_string updates are also
fixing bugs because the old code forgot to cast the input to uchar
first. That meant the compiler was generating sign-extension from 8 to
16 bits, as opposed to zero-extension.

Change-Id: I4e2430a51dfc337994834524d3540382157509ef
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Move the code that converts from UTF-16 to Latin1 to the top

Just so it's closer to the code that does the inverse.

Change-Id: Iecaab20adad2cb7f4a55818c687aecc76f0523e7
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Reviewed-by: Frederik Gladhorn <frederik.gladhorn@digia.com>
Q(Plain)TextEdit: Add find() overload with QRegExp

Add overloads to the find() methods in QPlainTextEdit and QTextEdit
that find the next occurrence matching the passed regular expression.

These are convenience methods that eliminate the need to use the
document() method and the need to handle the QTextCursor return value.

[ChangeLog][QtWidgets][QPlainTextEdit] Added find method overload using QRegExp

[ChangeLog][QtWidgets][QTextEdit] Added find method overload using QRegExp

Change-Id: Ia6139b771e3ae4ca02e4b8ea7fde19e5dc71b9d8
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>