1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package norm
6
7type valueRange struct {
8	value  uint16 // header: value:stride
9	lo, hi byte   // header: lo:n
10}
11
12type sparseBlocks struct {
13	values []valueRange
14	offset []uint16
15}
16
17var nfcSparse = sparseBlocks{
18	values: nfcSparseValues[:],
19	offset: nfcSparseOffset[:],
20}
21
22var nfkcSparse = sparseBlocks{
23	values: nfkcSparseValues[:],
24	offset: nfkcSparseOffset[:],
25}
26
27var (
28	nfcData  = newNfcTrie(0)
29	nfkcData = newNfkcTrie(0)
30)
31
32// lookupValue determines the type of block n and looks up the value for b.
33// For n < t.cutoff, the block is a simple lookup table. Otherwise, the block
34// is a list of ranges with an accompanying value. Given a matching range r,
35// the value for b is by r.value + (b - r.lo) * stride.
36func (t *sparseBlocks) lookup(n uint32, b byte) uint16 {
37	offset := t.offset[n]
38	header := t.values[offset]
39	lo := offset + 1
40	hi := lo + uint16(header.lo)
41	for lo < hi {
42		m := lo + (hi-lo)/2
43		r := t.values[m]
44		if r.lo <= b && b <= r.hi {
45			return r.value + uint16(b-r.lo)*header.value
46		}
47		if b < r.lo {
48			hi = m
49		} else {
50			lo = m + 1
51		}
52	}
53	return 0
54}
55