Blame src/lookup_string_in_fixed_set.c

Packit Service dcb6c2
/* Copyright 2015-2016 The Chromium Authors. All rights reserved.
Packit Service dcb6c2
 * Use of this source code is governed by a BSD-style license that can be
Packit Service dcb6c2
 * found in the LICENSE.chromium file.
Packit Service dcb6c2
 *
Packit Service dcb6c2
 * Converted to C89 2015 by Tim Rühsen
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
#include <stddef.h>
Packit Service dcb6c2
Packit Service dcb6c2
#if defined(__GNUC__) && defined(__GNUC_MINOR__)
Packit Service dcb6c2
#       define _GCC_VERSION_AT_LEAST(major, minor) ((__GNUC__ > (major)) || (__GNUC__ == (major) && __GNUC_MINOR__ >= (minor)))
Packit Service dcb6c2
#else
Packit Service dcb6c2
#       define _GCC_VERSION_AT_LEAST(major, minor) 0
Packit Service dcb6c2
#endif
Packit Service dcb6c2
Packit Service dcb6c2
#define CHECK_LT(a, b) if ((a) >= b) return 0
Packit Service dcb6c2
Packit Service dcb6c2
static const char multibyte_length_table[16] = {
Packit Service dcb6c2
	0, 0, 0, 0,	 /* 0x00-0x3F */
Packit Service dcb6c2
	0, 0, 0, 0,	 /* 0x40-0x7F */
Packit Service dcb6c2
	0, 0, 0, 0,	 /* 0x80-0xBF */
Packit Service dcb6c2
	2, 2, 3, 4,	 /* 0xC0-0xFF */
Packit Service dcb6c2
};
Packit Service dcb6c2
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Get length of multibyte character sequence starting at a given byte.
Packit Service dcb6c2
 * Returns zero if the byte is not a valid leading byte in UTF-8.
Packit Service dcb6c2
 */
Packit Service dcb6c2
static int GetMultibyteLength(char c) {
Packit Service dcb6c2
	return multibyte_length_table[((unsigned char)c) >> 4];
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Moves pointers one byte forward.
Packit Service dcb6c2
 */
Packit Service dcb6c2
static void NextPos(const unsigned char** pos,
Packit Service dcb6c2
	const char** key,
Packit Service dcb6c2
	const char** multibyte_start)
Packit Service dcb6c2
{
Packit Service dcb6c2
	++*pos;
Packit Service dcb6c2
	if (*multibyte_start) {
Packit Service dcb6c2
		/* Advance key to next byte in multibyte sequence. */
Packit Service dcb6c2
		++*key;
Packit Service dcb6c2
		/* Reset multibyte_start if last byte in multibyte sequence was consumed. */
Packit Service dcb6c2
		if (*key - *multibyte_start == GetMultibyteLength(**multibyte_start))
Packit Service dcb6c2
			*multibyte_start = 0;
Packit Service dcb6c2
	} else {
Packit Service dcb6c2
		if (GetMultibyteLength(**key)) {
Packit Service dcb6c2
			/* Multibyte prefix was matched in the dafsa, start matching multibyte
Packit Service dcb6c2
			 * content in next round. */
Packit Service dcb6c2
			*multibyte_start = *key;
Packit Service dcb6c2
		} else {
Packit Service dcb6c2
			/* Advance key as a single byte character was matched. */
Packit Service dcb6c2
			++*key;
Packit Service dcb6c2
		}
Packit Service dcb6c2
	}
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Read next offset from pos.
Packit Service dcb6c2
 * Returns true if an offset could be read, false otherwise.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
static int GetNextOffset(const unsigned char** pos,
Packit Service dcb6c2
	const unsigned char* end,
Packit Service dcb6c2
	const unsigned char** offset)
Packit Service dcb6c2
{
Packit Service dcb6c2
	size_t bytes_consumed;
Packit Service dcb6c2
Packit Service dcb6c2
	if (*pos == end)
Packit Service dcb6c2
		return 0;
Packit Service dcb6c2
Packit Service dcb6c2
	/* When reading an offset the byte array must always contain at least
Packit Service dcb6c2
	 * three more bytes to consume. First the offset to read, then a node
Packit Service dcb6c2
	 * to skip over and finally a destination node. No object can be smaller
Packit Service dcb6c2
	 * than one byte. */
Packit Service dcb6c2
	CHECK_LT(*pos + 2, end);
Packit Service dcb6c2
	switch (**pos & 0x60) {
Packit Service dcb6c2
	case 0x60: /* Read three byte offset */
Packit Service dcb6c2
		*offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2];
Packit Service dcb6c2
		bytes_consumed = 3;
Packit Service dcb6c2
		break;
Packit Service dcb6c2
	case 0x40: /* Read two byte offset */
Packit Service dcb6c2
		*offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1];
Packit Service dcb6c2
		bytes_consumed = 2;
Packit Service dcb6c2
		break;
Packit Service dcb6c2
	default:
Packit Service dcb6c2
		*offset += (*pos)[0] & 0x3F;
Packit Service dcb6c2
		bytes_consumed = 1;
Packit Service dcb6c2
	}
Packit Service dcb6c2
	if ((**pos & 0x80) != 0) {
Packit Service dcb6c2
		*pos = end;
Packit Service dcb6c2
	} else {
Packit Service dcb6c2
		*pos += bytes_consumed;
Packit Service dcb6c2
	}
Packit Service dcb6c2
	return 1;
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Check if byte at offset is last in label.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
static int IsEOL(const unsigned char* offset, const unsigned char* end)
Packit Service dcb6c2
{
Packit Service dcb6c2
	CHECK_LT(offset, end);
Packit Service dcb6c2
	return(*offset & 0x80) != 0;
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Check if byte at offset matches first character in key.
Packit Service dcb6c2
 * This version assumes a range check was already performed by the caller.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
static int IsMatchUnchecked(const unsigned char matcher,
Packit Service dcb6c2
	const char* key,
Packit Service dcb6c2
	const char* multibyte_start)
Packit Service dcb6c2
{
Packit Service dcb6c2
	if (multibyte_start) {
Packit Service dcb6c2
		/* Multibyte matching mode. */
Packit Service dcb6c2
		if (multibyte_start == key) {
Packit Service dcb6c2
			/* Match leading byte, which will also match the sequence length. */
Packit Service dcb6c2
			return (matcher ^ 0x80) == (const unsigned char)*key;
Packit Service dcb6c2
		} else {
Packit Service dcb6c2
			/* Match following bytes. */
Packit Service dcb6c2
			return (matcher ^ 0xC0) == (const unsigned char)*key;
Packit Service dcb6c2
		}
Packit Service dcb6c2
	}
Packit Service dcb6c2
	/* If key points at a leading byte in a multibyte sequence, but we are not yet
Packit Service dcb6c2
	 * in multibyte mode, then the dafsa should contain a special byte to indicate
Packit Service dcb6c2
	 * a mode switch. */
Packit Service dcb6c2
	if (GetMultibyteLength(*key)) {
Packit Service dcb6c2
		return matcher == 0x1F;
Packit Service dcb6c2
	}
Packit Service dcb6c2
	/* Normal matching of a single byte character. */
Packit Service dcb6c2
	return matcher == (const unsigned char)*key;
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Check if byte at offset matches first character in key.
Packit Service dcb6c2
 * This version matches characters not last in label.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
static int IsMatch(const unsigned char* offset,
Packit Service dcb6c2
	const unsigned char* end,
Packit Service dcb6c2
	const char* key,
Packit Service dcb6c2
	const char* multibyte_start)
Packit Service dcb6c2
{
Packit Service dcb6c2
	CHECK_LT(offset, end);
Packit Service dcb6c2
	return IsMatchUnchecked(*offset, key, multibyte_start);
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Check if byte at offset matches first character in key.
Packit Service dcb6c2
 * This version matches characters last in label.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
static int IsEndCharMatch(const unsigned char* offset,
Packit Service dcb6c2
	const unsigned char* end,
Packit Service dcb6c2
	const char* key,
Packit Service dcb6c2
	const char* multibyte_start)
Packit Service dcb6c2
{
Packit Service dcb6c2
	CHECK_LT(offset, end);
Packit Service dcb6c2
	return IsMatchUnchecked(*offset ^ 0x80, key, multibyte_start);
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 * Read return value at offset.
Packit Service dcb6c2
 * Returns true if a return value could be read, false otherwise.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
static int GetReturnValue(const unsigned char* offset,
Packit Service dcb6c2
	const unsigned char* end,
Packit Service dcb6c2
	const char* multibyte_start,
Packit Service dcb6c2
	int* return_value)
Packit Service dcb6c2
{
Packit Service dcb6c2
	CHECK_LT(offset, end);
Packit Service dcb6c2
	if (!multibyte_start && (*offset & 0xE0) == 0x80) {
Packit Service dcb6c2
		*return_value = *offset & 0x0F;
Packit Service dcb6c2
		return 1;
Packit Service dcb6c2
	}
Packit Service dcb6c2
	return 0;
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/*
Packit Service dcb6c2
 *  Looks up the string |key| with length |key_length| in a fixed set of
Packit Service dcb6c2
 * strings. The set of strings must be known at compile time. It is converted to
Packit Service dcb6c2
 * a graph structure named a DAFSA (Deterministic Acyclic Finite State
Packit Service dcb6c2
 * Automaton) by the script psl-make-dafsa during compilation. This permits
Packit Service dcb6c2
 * efficient (in time and space) lookup. The graph generated by psl-make-dafsa
Packit Service dcb6c2
 * takes the form of a constant byte array which should be supplied via the
Packit Service dcb6c2
 * |graph| and |length| parameters.  The return value is kDafsaNotFound,
Packit Service dcb6c2
 * kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule,
Packit Service dcb6c2
 * kDafsaWildcardRule and kDafsaPrivateRule ORed together.
Packit Service dcb6c2
 * 
Packit Service dcb6c2
 * Lookup a domain key in a byte array generated by psl-make-dafsa.
Packit Service dcb6c2
 */
Packit Service dcb6c2
Packit Service dcb6c2
/* prototype to skip warning with -Wmissing-prototypes */
Packit Service dcb6c2
int LookupStringInFixedSet(const unsigned char*, size_t,const char*, size_t);
Packit Service dcb6c2
Packit Service dcb6c2
int LookupStringInFixedSet(const unsigned char* graph,
Packit Service dcb6c2
	size_t length,
Packit Service dcb6c2
	const char* key,
Packit Service dcb6c2
	size_t key_length)
Packit Service dcb6c2
{
Packit Service dcb6c2
	const unsigned char* pos = graph;
Packit Service dcb6c2
	const unsigned char* end = graph + length;
Packit Service dcb6c2
	const unsigned char* offset = pos;
Packit Service dcb6c2
	const char* key_end = key + key_length;
Packit Service dcb6c2
	const char* multibyte_start = 0;
Packit Service dcb6c2
Packit Service dcb6c2
	while (GetNextOffset(&pos, end, &offset)) {
Packit Service dcb6c2
		/*char <char>+ end_char offsets
Packit Service dcb6c2
		 * char <char>+ return value
Packit Service dcb6c2
		 * char end_char offsets
Packit Service dcb6c2
		 * char return value
Packit Service dcb6c2
		 * end_char offsets
Packit Service dcb6c2
		 * return_value
Packit Service dcb6c2
		 */
Packit Service dcb6c2
		int did_consume = 0;
Packit Service dcb6c2
Packit Service dcb6c2
		if (key != key_end && !IsEOL(offset, end)) {
Packit Service dcb6c2
			/* Leading <char> is not a match. Don't dive into this child */
Packit Service dcb6c2
			if (!IsMatch(offset, end, key, multibyte_start))
Packit Service dcb6c2
				continue;
Packit Service dcb6c2
			did_consume = 1;
Packit Service dcb6c2
			NextPos(&offset, &key, &multibyte_start);
Packit Service dcb6c2
			/* Possible matches at this point:
Packit Service dcb6c2
			 * <char>+ end_char offsets
Packit Service dcb6c2
			 * <char>+ return value
Packit Service dcb6c2
			 * end_char offsets
Packit Service dcb6c2
			 * return value
Packit Service dcb6c2
			 */
Packit Service dcb6c2
Packit Service dcb6c2
			/* Remove all remaining <char> nodes possible */
Packit Service dcb6c2
			while (!IsEOL(offset, end) && key != key_end) {
Packit Service dcb6c2
				if (!IsMatch(offset, end, key, multibyte_start))
Packit Service dcb6c2
					return -1;
Packit Service dcb6c2
				NextPos(&offset, &key, &multibyte_start);
Packit Service dcb6c2
			}
Packit Service dcb6c2
		}
Packit Service dcb6c2
		/* Possible matches at this point:
Packit Service dcb6c2
		 * end_char offsets
Packit Service dcb6c2
		 * return_value
Packit Service dcb6c2
		 * If one or more <char> elements were consumed, a failure
Packit Service dcb6c2
		 * to match is terminal. Otherwise, try the next node.
Packit Service dcb6c2
		 */
Packit Service dcb6c2
		if (key == key_end) {
Packit Service dcb6c2
			int return_value;
Packit Service dcb6c2
Packit Service dcb6c2
			if (GetReturnValue(offset, end, multibyte_start, &return_value))
Packit Service dcb6c2
				return return_value;
Packit Service dcb6c2
			/* The DAFSA guarantees that if the first char is a match, all
Packit Service dcb6c2
			 * remaining char elements MUST match if the key is truly present.
Packit Service dcb6c2
			 */
Packit Service dcb6c2
			if (did_consume)
Packit Service dcb6c2
				return -1;
Packit Service dcb6c2
			continue;
Packit Service dcb6c2
		}
Packit Service dcb6c2
		if (!IsEndCharMatch(offset, end, key, multibyte_start)) {
Packit Service dcb6c2
			if (did_consume)
Packit Service dcb6c2
				return -1; /* Unexpected */
Packit Service dcb6c2
			continue;
Packit Service dcb6c2
		}
Packit Service dcb6c2
		NextPos(&offset, &key, &multibyte_start);
Packit Service dcb6c2
		pos = offset; /* Dive into child */
Packit Service dcb6c2
	}
Packit Service dcb6c2
Packit Service dcb6c2
	return -1; /* No match */
Packit Service dcb6c2
}
Packit Service dcb6c2
Packit Service dcb6c2
/* prototype to skip warning with -Wmissing-prototypes */
Packit Service dcb6c2
int GetUtfMode(const unsigned char *graph, size_t length);
Packit Service dcb6c2
Packit Service dcb6c2
int GetUtfMode(const unsigned char *graph, size_t length)
Packit Service dcb6c2
{
Packit Service dcb6c2
	return length > 0 && graph[length - 1] < 0x80;
Packit Service dcb6c2
}