[pcsx_rearmed.git] / deps / lightning / lib / jit_note.c

/*
 * Copyright (C) 2013-2023  Free Software Foundation, Inc.
 *
 * This file is part of GNU lightning.
 *
 * GNU lightning is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation; either version 3, or (at your option)
 * any later version.
 *
 * GNU lightning is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include <lightning.h>
#include <lightning/jit_private.h>

/*
 * Prototypes
 */
#define new_note(u, v)		_new_note(_jit, u, v)
static jit_note_t *_new_note(jit_state_t *, jit_uint8_t*, char*);
static void new_line(jit_int32_t,jit_note_t*,char*,jit_int32_t,jit_int32_t);
#define note_search_index(u)	_note_search_index(_jit, u)
static jit_int32_t _note_search_index(jit_state_t*, jit_uint8_t*);
static jit_int32_t line_insert_index(jit_note_t*,jit_int32_t);
static jit_int32_t line_search_index(jit_note_t*,jit_int32_t);
static jit_int32_t offset_insert_index(jit_line_t*,jit_int32_t);
static jit_int32_t offset_search_index(jit_line_t*,jit_int32_t);

/*
 * Implementation
 */
void
jit_init_note(void)
{
}

void
jit_finish_note(void)
{
}

jit_node_t *
_jit_name(jit_state_t *_jit, const char *name)
{
    jit_node_t		*node;

    node = jit_new_node(jit_code_name);
    if (name)
	node->v.n = jit_data(name, strlen(name) + 1, 1);
    else
	node->v.p = NULL;
    if (_jitc->note.head == NULL)
	_jitc->note.head = _jitc->note.tail = node;
    else {
	_jitc->note.tail->link = node;
	_jitc->note.tail = node;
    }
    ++_jit->note.length;
    _jitc->note.size += sizeof(jit_note_t);
    /* remember previous note is invalid due to name change */
    _jitc->note.note = NULL;
    return (_jitc->note.name = node);
}

jit_node_t *
_jit_note(jit_state_t *_jit, const char *name, int line)
{
    jit_node_t		*node;

    node = jit_new_node(jit_code_note);
    if (name)
	node->v.n = jit_data(name, strlen(name) + 1, 1);
    else
	node->v.p = NULL;
    node->w.w = line;
    if (_jitc->note.head == NULL)
	_jitc->note.head = _jitc->note.tail = node;
    else {
	_jitc->note.tail->link = node;
	_jitc->note.tail = node;
    }
    if (_jitc->note.note == NULL ||
	(name == NULL && _jitc->note.note != NULL) ||
	(name != NULL && _jitc->note.note == NULL) ||
	(name != NULL && _jitc->note.note != NULL &&
	 strcmp(name, (char *)_jitc->data.ptr + _jitc->note.note->v.n->u.w)))
	_jitc->note.size += sizeof(jit_line_t);
    _jitc->note.size += sizeof(jit_int32_t) * 2;
    return (_jitc->note.note = node);
}

void
_jit_annotate(jit_state_t *_jit)
{
    jit_node_t		*node;
    jit_note_t		*note;
    jit_line_t		*line;
    jit_word_t		 length;
    jit_word_t		 note_offset;
    jit_word_t		 line_offset;

    /* initialize pointers in mmaped data area */
    _jit->note.ptr = (jit_note_t *)_jitc->note.base;
    _jit->note.length = 0;

    note = NULL;
    for (node = _jitc->note.head; node; node = node->link) {
	if (node->code == jit_code_name)
	    note = new_note(node->u.p, node->v.p ? node->v.n->u.p : NULL);
	else if (node->v.p) {
	    if (note == NULL)
		note = new_note(node->u.p, NULL);
	    jit_set_note(note, node->v.n->u.p, node->w.w,
			 (jit_uint8_t *)node->u.p - note->code);
	}
    }
    /* last note */
    if (note)
	note->size = _jit->pc.uc - note->code;

    /* annotations may be very complex with conditions to extend
     * or ignore redundant notes, as well as add entries to earlier
     * notes, so, relocate the information to the data buffer,
     * with likely over allocated reserved space */

    /* relocate jit_line_t objects */
    for (note_offset = 0; note_offset < _jit->note.length; note_offset++) {
	note = _jit->note.ptr + note_offset;
	if ((length = sizeof(jit_line_t) * note->length) == 0)
	    continue;
	assert(_jitc->note.base + length <= _jit->data.ptr + _jit->data.length);
	jit_memcpy(_jitc->note.base, note->lines, length);
	jit_free((jit_pointer_t *)&note->lines);
	note->lines = (jit_line_t *)_jitc->note.base;
	_jitc->note.base += length;
    }

    /* relocate offset and line number information */
    for (note_offset = 0; note_offset < _jit->note.length; note_offset++) {
	note = _jit->note.ptr + note_offset;
	for (line_offset = 0; line_offset < note->length; line_offset++) {
	    line = note->lines + line_offset;
	    length = sizeof(jit_int32_t) * line->length;
	    assert(_jitc->note.base + length <=
		   _jit->data.ptr + _jit->data.length);
	    jit_memcpy(_jitc->note.base, line->linenos, length);
	    jit_free((jit_pointer_t *)&line->linenos);
	    line->linenos = (jit_int32_t *)_jitc->note.base;
	    _jitc->note.base += length;
	    assert(_jitc->note.base + length <=
		   _jit->data.ptr + _jit->data.length);
	    jit_memcpy(_jitc->note.base, line->offsets, length);
	    jit_free((jit_pointer_t *)&line->offsets);
	    line->offsets = (jit_int32_t *)_jitc->note.base;
	    _jitc->note.base += length;
	}
    }
}

void
_jit_set_note(jit_state_t *_jit, jit_note_t *note,
	      char *file, int lineno, jit_int32_t offset)
{
    jit_line_t		*line;
    jit_int32_t		 index;

    index = line_insert_index(note, offset);
    if (note->length && index == note->length &&
	note->lines[index - 1].file == file)
	--index;
    if (index >= note->length || note->lines[index].file != file)
	new_line(index, note, file, lineno, offset);
    else {
	line = note->lines + index;
	index = offset_insert_index(line, offset);
	if (index < line->length && line->offsets[index] == offset) {
	    /* common case if no code was generated for several source lines */
	    if (line->linenos[index] < lineno)
		line->linenos[index] = lineno;
	}
	else if (index < line->length && line->linenos[index] == lineno) {
	    /* common case of extending entry */
	    if (line->offsets[index] > offset)
		line->offsets[index] = offset;
	}
	else {
	    /* line or offset changed */
	    if ((line->length & 15) == 0) {
		jit_realloc((jit_pointer_t *)&line->linenos,
			    line->length * sizeof(jit_int32_t),
			    (line->length + 17) * sizeof(jit_int32_t));
		jit_realloc((jit_pointer_t *)&line->offsets,
			    line->length * sizeof(jit_int32_t),
			    (line->length + 17) * sizeof(jit_int32_t));
	    }
	    if (index < note->length) {
		jit_memmove(line->linenos + index + 1, line->linenos + index,
			    sizeof(jit_int32_t) * (line->length - index));
		jit_memmove(line->offsets + index + 1, line->offsets + index,
			    sizeof(jit_int32_t) * (line->length - index));
	    }
	    line->linenos[index] = lineno;
	    line->offsets[index] = offset;
	    ++line->length;
	}
    }
}

jit_bool_t
_jit_get_note(jit_state_t *_jit, jit_pointer_t code,
	      char **name, char **file, jit_int32_t *lineno)
{
    jit_note_t		*note;
    jit_line_t		*line;
    jit_int32_t		 index;
    jit_int32_t		 offset;

    if ((index = note_search_index((jit_uint8_t *)code)) >= _jit->note.length)
	return (0);
    note = _jit->note.ptr + index;
    if ((jit_uint8_t *)code < note->code ||
	(jit_uint8_t *)code >= note->code + note->size)
	return (0);
    offset = (jit_uint8_t *)code - note->code;
    if ((index = line_search_index(note, offset)) >= note->length)
	return (0);
    if (index == 0 && offset < note->lines[0].offsets[0])
	return (0);
    line = note->lines + index;
    if ((index = offset_search_index(line, offset)) >= line->length)
	return (0);

    if (name)
	*name = note->name;
    if (file)
	*file = line->file;
    if (lineno)
	*lineno = line->linenos[index];

    return (1);
}

static jit_note_t *
_new_note(jit_state_t *_jit, jit_uint8_t *code, char *name)
{
    jit_note_t		*note;
    jit_note_t		*prev;

    if (_jit->note.length) {
	prev = _jit->note.ptr + _jit->note.length - 1;
	assert(code >= prev->code);
	prev->size = code - prev->code;
    }
    note = (jit_note_t *)_jitc->note.base;
    _jitc->note.base += sizeof(jit_note_t);
    ++_jit->note.length;
    note->code = code;
    note->name = name;

    return (note);
}

static void
new_line(jit_int32_t index, jit_note_t *note,
	  char *file, jit_int32_t lineno, jit_int32_t offset)
{
    jit_line_t		*line;

    if (note->lines == NULL)
	jit_alloc((jit_pointer_t *)&note->lines, 16 * sizeof(jit_line_t));
    else if ((note->length & 15) == 15)
	jit_realloc((jit_pointer_t *)&note->lines,
		    note->length * sizeof(jit_line_t),
		    (note->length + 17) * sizeof(jit_line_t));

    if (index < note->length)
	jit_memmove(note->lines + index + 1, note->lines + index,
		    sizeof(jit_line_t) * (note->length - index));
    line = note->lines + index;
    ++note->length;

    line->file = file;
    line->length = 1;
    jit_alloc((jit_pointer_t *)&line->linenos, 16 * sizeof(jit_int32_t));
    line->linenos[0] = lineno;
    jit_alloc((jit_pointer_t *)&line->offsets, 16 * sizeof(jit_int32_t));
    line->offsets[0] = offset;
}

static jit_int32_t
_note_search_index(jit_state_t *_jit, jit_uint8_t *code)
{
    jit_int32_t		 bot;
    jit_int32_t		 top;
    jit_int32_t		 index;
    jit_note_t		*notes;

    bot = 0;
    top = _jit->note.length;
    notes = _jit->note.ptr;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (code < notes[index].code)
	    top = index;
	else if (code >= notes[index].code &&
		 code - notes[index].code < notes[index].size)
	    break;
	else
	    bot = index + 1;
    }

    return (index);
}

static jit_int32_t
line_insert_index(jit_note_t *note, jit_int32_t offset)
{
    jit_int32_t		 bot;
    jit_int32_t		 top;
    jit_int32_t		 index;
    jit_line_t		*lines;

    bot = 0;
    top = note->length;
    if ((lines = note->lines) == NULL)
	return (0);
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < *lines[index].offsets)
	    top = index;
	else
	    bot = index + 1;
    }

    return ((bot + top) >> 1);
}

static jit_int32_t
line_search_index(jit_note_t *note, jit_int32_t offset)
{
    jit_int32_t		 bot;
    jit_int32_t		 top;
    jit_int32_t		 index;
    jit_line_t		*lines;

    bot = 0;
    top = note->length;
    if ((lines = note->lines) == NULL)
	return (0);
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < *lines[index].offsets)
	    top = index;
	/* offset should be already verified to be in range */
	else if (index == note->length - 1 ||
		 (offset >= *lines[index].offsets &&
		  offset < *lines[index + 1].offsets))
	    break;
	else
	    bot = index + 1;
    }

    return (index);
}

static jit_int32_t
offset_insert_index(jit_line_t *line, jit_int32_t offset)
{
    jit_int32_t		 bot;
    jit_int32_t		 top;
    jit_int32_t		 index;
    jit_int32_t		*offsets;

    bot = 0;
    top = line->length;
    offsets = line->offsets;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < offsets[index])
	    top = index;
	else
	    bot = index + 1;
    }

    return ((bot + top) >> 1);
}

static jit_int32_t
offset_search_index(jit_line_t *line, jit_int32_t offset)
{
    jit_int32_t		 bot;
    jit_int32_t		 top;
    jit_int32_t		 index;
    jit_int32_t		*offsets;

    bot = 0;
    top = line->length;
    offsets = line->offsets;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < offsets[index])
	    top = index;
	/* offset should be already verified to be in range */
	else if (index == line->length - 1 ||
		 (offset >= offsets[index] && offset < offsets[index + 1]))
	    break;
	else
	    bot = index + 1;
    }

    return (index);
}
Commit	Line	Data
4a71579b	1	/*
79bfeef6	2	* Copyright (C) 2013-2023 Free Software Foundation, Inc.
4a71579b PC	3	*
	4	* This file is part of GNU lightning.
	5	*
	6	* GNU lightning is free software; you can redistribute it and/or modify it
	7	* under the terms of the GNU Lesser General Public License as published
	8	* by the Free Software Foundation; either version 3, or (at your option)
	9	* any later version.
	10	*
	11	* GNU lightning is distributed in the hope that it will be useful, but
	12	* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	13	* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
	14	* License for more details.
	15	*
	16	* Authors:
	17	* Paulo Cesar Pereira de Andrade
	18	*/
	19
	20	#include <lightning.h>
	21	#include <lightning/jit_private.h>
	22
	23	/*
	24	* Prototypes
	25	*/
	26	#define new_note(u, v) _new_note(_jit, u, v)
	27	static jit_note_t _new_note(jit_state_t , jit_uint8_t, char);
	28	static void new_line(jit_int32_t,jit_note_t,char,jit_int32_t,jit_int32_t);
	29	#define note_search_index(u) _note_search_index(_jit, u)
	30	static jit_int32_t _note_search_index(jit_state_t, jit_uint8_t);
	31	static jit_int32_t line_insert_index(jit_note_t*,jit_int32_t);
	32	static jit_int32_t line_search_index(jit_note_t*,jit_int32_t);
	33	static jit_int32_t offset_insert_index(jit_line_t*,jit_int32_t);
	34	static jit_int32_t offset_search_index(jit_line_t*,jit_int32_t);
	35
	36	/*
	37	* Implementation
	38	*/
	39	void
	40	jit_init_note(void)
	41	{
	42	}
	43
	44	void
	45	jit_finish_note(void)
	46	{
	47	}
	48
	49	jit_node_t *
	50	_jit_name(jit_state_t _jit, const char name)
	51	{
	52	jit_node_t *node;
	53
	54	node = jit_new_node(jit_code_name);
	55	if (name)
	56	node->v.n = jit_data(name, strlen(name) + 1, 1);
	57	else
	58	node->v.p = NULL;
	59	if (_jitc->note.head == NULL)
	60	_jitc->note.head = _jitc->note.tail = node;
	61	else {
	62	_jitc->note.tail->link = node;
	63	_jitc->note.tail = node;
	64	}
	65	++_jit->note.length;
	66	_jitc->note.size += sizeof(jit_note_t);
67	/* remember previous note is invalid due to name change */
68	_jitc->note.note = NULL;
69	return (_jitc->note.name = node);
70	}
71
72	jit_node_t *
73	_jit_note(jit_state_t _jit, const char name, int line)
74	{
75	jit_node_t *node;
76
77	node = jit_new_node(jit_code_note);
78	if (name)
79	node->v.n = jit_data(name, strlen(name) + 1, 1);
80	else
81	node->v.p = NULL;
82	node->w.w = line;
83	if (_jitc->note.head == NULL)
84	_jitc->note.head = _jitc->note.tail = node;
85	else {
86	_jitc->note.tail->link = node;
87	_jitc->note.tail = node;
88	}
89	if (_jitc->note.note == NULL \|\|
90	(name == NULL && _jitc->note.note != NULL) \|\|
91	(name != NULL && _jitc->note.note == NULL) \|\|
92	(name != NULL && _jitc->note.note != NULL &&
93	strcmp(name, (char *)_jitc->data.ptr + _jitc->note.note->v.n->u.w)))
94	_jitc->note.size += sizeof(jit_line_t);
95	_jitc->note.size += sizeof(jit_int32_t) * 2;
96	return (_jitc->note.note = node);
97	}
98
99	void
100	_jit_annotate(jit_state_t *_jit)
101	{
102	jit_node_t *node;
103	jit_note_t *note;
104	jit_line_t *line;
105	jit_word_t length;
106	jit_word_t note_offset;
107	jit_word_t line_offset;
108
109	/* initialize pointers in mmaped data area */
110	_jit->note.ptr = (jit_note_t *)_jitc->note.base;
111	_jit->note.length = 0;
112
113	note = NULL;
114	for (node = _jitc->note.head; node; node = node->link) {
115	if (node->code == jit_code_name)
116	note = new_note(node->u.p, node->v.p ? node->v.n->u.p : NULL);
117	else if (node->v.p) {
118	if (note == NULL)
119	note = new_note(node->u.p, NULL);
120	jit_set_note(note, node->v.n->u.p, node->w.w,
121	(jit_uint8_t *)node->u.p - note->code);
122	}
123	}
124	/* last note */
125	if (note)
126	note->size = _jit->pc.uc - note->code;
127
128	/* annotations may be very complex with conditions to extend
129	* or ignore redundant notes, as well as add entries to earlier
130	* notes, so, relocate the information to the data buffer,
131	* with likely over allocated reserved space */
132
133	/* relocate jit_line_t objects */
134	for (note_offset = 0; note_offset < _jit->note.length; note_offset++) {
135	note = _jit->note.ptr + note_offset;
136	if ((length = sizeof(jit_line_t) * note->length) == 0)
137	continue;
ba86ff93	138	assert(_jitc->note.base + length <= _jit->data.ptr + _jit->data.length);
4a71579b PC	139	jit_memcpy(_jitc->note.base, note->lines, length);
	140	jit_free((jit_pointer_t *)&note->lines);
	141	note->lines = (jit_line_t *)_jitc->note.base;
	142	_jitc->note.base += length;
	143	}
	144
	145	/* relocate offset and line number information */
	146	for (note_offset = 0; note_offset < _jit->note.length; note_offset++) {
	147	note = _jit->note.ptr + note_offset;
	148	for (line_offset = 0; line_offset < note->length; line_offset++) {
	149	line = note->lines + line_offset;
	150	length = sizeof(jit_int32_t) * line->length;
ba86ff93	151	assert(_jitc->note.base + length <=
4a71579b PC	152	_jit->data.ptr + _jit->data.length);
	153	jit_memcpy(_jitc->note.base, line->linenos, length);
	154	jit_free((jit_pointer_t *)&line->linenos);
	155	line->linenos = (jit_int32_t *)_jitc->note.base;
	156	_jitc->note.base += length;
ba86ff93	157	assert(_jitc->note.base + length <=
4a71579b PC	158	_jit->data.ptr + _jit->data.length);
	159	jit_memcpy(_jitc->note.base, line->offsets, length);
	160	jit_free((jit_pointer_t *)&line->offsets);
	161	line->offsets = (jit_int32_t *)_jitc->note.base;
	162	_jitc->note.base += length;
	163	}
	164	}
	165	}
	166
	167	void
	168	_jit_set_note(jit_state_t _jit, jit_note_t note,
	169	char *file, int lineno, jit_int32_t offset)
	170	{
	171	jit_line_t *line;
	172	jit_int32_t index;
	173
	174	index = line_insert_index(note, offset);
	175	if (note->length && index == note->length &&
	176	note->lines[index - 1].file == file)
	177	--index;
	178	if (index >= note->length \|\| note->lines[index].file != file)
	179	new_line(index, note, file, lineno, offset);
	180	else {
	181	line = note->lines + index;
	182	index = offset_insert_index(line, offset);
	183	if (index < line->length && line->offsets[index] == offset) {
	184	/* common case if no code was generated for several source lines */
	185	if (line->linenos[index] < lineno)
	186	line->linenos[index] = lineno;
	187	}
	188	else if (index < line->length && line->linenos[index] == lineno) {
	189	/* common case of extending entry */
	190	if (line->offsets[index] > offset)
	191	line->offsets[index] = offset;
	192	}
	193	else {
	194	/* line or offset changed */
	195	if ((line->length & 15) == 0) {
	196	jit_realloc((jit_pointer_t *)&line->linenos,
	197	line->length * sizeof(jit_int32_t),
	198	(line->length + 17) * sizeof(jit_int32_t));
	199	jit_realloc((jit_pointer_t *)&line->offsets,
	200	line->length * sizeof(jit_int32_t),
	201	(line->length + 17) * sizeof(jit_int32_t));
	202	}
	203	if (index < note->length) {
	204	jit_memmove(line->linenos + index + 1, line->linenos + index,
	205	sizeof(jit_int32_t) * (line->length - index));
	206	jit_memmove(line->offsets + index + 1, line->offsets + index,
	207	sizeof(jit_int32_t) * (line->length - index));
	208	}
	209	line->linenos[index] = lineno;
	210	line->offsets[index] = offset;
	211	++line->length;
	212	}
	213	}
	214	}
	215
	216	jit_bool_t
	217	_jit_get_note(jit_state_t *_jit, jit_pointer_t code,
	218	char name, char file, jit_int32_t *lineno)
	219	{
	220	jit_note_t *note;
	221	jit_line_t *line;
222	jit_int32_t index;
223	jit_int32_t offset;
224
225	if ((index = note_search_index((jit_uint8_t *)code)) >= _jit->note.length)
226	return (0);
227	note = _jit->note.ptr + index;
228	if ((jit_uint8_t *)code < note->code \|\|
229	(jit_uint8_t *)code >= note->code + note->size)
230	return (0);
231	offset = (jit_uint8_t *)code - note->code;
232	if ((index = line_search_index(note, offset)) >= note->length)
233	return (0);
234	if (index == 0 && offset < note->lines[0].offsets[0])
235	return (0);
236	line = note->lines + index;
237	if ((index = offset_search_index(line, offset)) >= line->length)
238	return (0);
239
240	if (name)
241	*name = note->name;
242	if (file)
243	*file = line->file;
244	if (lineno)
245	*lineno = line->linenos[index];
246
247	return (1);
248	}
249
250	static jit_note_t *
251	_new_note(jit_state_t _jit, jit_uint8_t code, char *name)
252	{
253	jit_note_t *note;
254	jit_note_t *prev;
255
256	if (_jit->note.length) {
257	prev = _jit->note.ptr + _jit->note.length - 1;
258	assert(code >= prev->code);
259	prev->size = code - prev->code;
260	}
261	note = (jit_note_t *)_jitc->note.base;
262	_jitc->note.base += sizeof(jit_note_t);
263	++_jit->note.length;
264	note->code = code;
265	note->name = name;
266
267	return (note);
268	}
269
270	static void
271	new_line(jit_int32_t index, jit_note_t *note,
272	char *file, jit_int32_t lineno, jit_int32_t offset)
273	{
274	jit_line_t *line;
275
276	if (note->lines == NULL)
277	jit_alloc((jit_pointer_t )&note->lines, 16 sizeof(jit_line_t));
278	else if ((note->length & 15) == 15)
279	jit_realloc((jit_pointer_t *)&note->lines,
280	note->length * sizeof(jit_line_t),
281	(note->length + 17) * sizeof(jit_line_t));
282
283	if (index < note->length)
284	jit_memmove(note->lines + index + 1, note->lines + index,
285	sizeof(jit_line_t) * (note->length - index));
286	line = note->lines + index;
287	++note->length;
288
289	line->file = file;
290	line->length = 1;
291	jit_alloc((jit_pointer_t )&line->linenos, 16 sizeof(jit_int32_t));
292	line->linenos[0] = lineno;
293	jit_alloc((jit_pointer_t )&line->offsets, 16 sizeof(jit_int32_t));
294	line->offsets[0] = offset;
295	}
296
297	static jit_int32_t
298	_note_search_index(jit_state_t _jit, jit_uint8_t code)
299	{
300	jit_int32_t bot;
301	jit_int32_t top;
302	jit_int32_t index;
303	jit_note_t *notes;
304
305	bot = 0;
306	top = _jit->note.length;
307	notes = _jit->note.ptr;
308	for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
309	if (code < notes[index].code)
310	top = index;
311	else if (code >= notes[index].code &&
312	code - notes[index].code < notes[index].size)
313	break;
314	else
315	bot = index + 1;
316	}
317
318	return (index);
319	}
320
321	static jit_int32_t
322	line_insert_index(jit_note_t *note, jit_int32_t offset)
323	{
324	jit_int32_t bot;
325	jit_int32_t top;
326	jit_int32_t index;
327	jit_line_t *lines;
328
329	bot = 0;
330	top = note->length;
331	if ((lines = note->lines) == NULL)
332	return (0);
333	for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
334	if (offset < *lines[index].offsets)
335	top = index;
336	else
337	bot = index + 1;
338	}
339
340	return ((bot + top) >> 1);
341	}
342
343	static jit_int32_t
344	line_search_index(jit_note_t *note, jit_int32_t offset)
345	{
346	jit_int32_t bot;
347	jit_int32_t top;
348	jit_int32_t index;
349	jit_line_t *lines;
350
351	bot = 0;
352	top = note->length;
353	if ((lines = note->lines) == NULL)
354	return (0);
355	for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
356	if (offset < *lines[index].offsets)
357	top = index;
358	/* offset should be already verified to be in range */
359	else if (index == note->length - 1 \|\|
360	(offset >= *lines[index].offsets &&
361	offset < *lines[index + 1].offsets))
362	break;
363	else
364	bot = index + 1;
365	}
366
367	return (index);
368	}
369
370	static jit_int32_t
371	offset_insert_index(jit_line_t *line, jit_int32_t offset)
372	{
373	jit_int32_t bot;
374	jit_int32_t top;
375	jit_int32_t index;
376	jit_int32_t *offsets;
377
378	bot = 0;
379	top = line->length;
380	offsets = line->offsets;
381	for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
382	if (offset < offsets[index])
383	top = index;
384	else
385	bot = index + 1;
386	}
387
388	return ((bot + top) >> 1);
389	}
390
391	static jit_int32_t
392	offset_search_index(jit_line_t *line, jit_int32_t offset)
393	{
394	jit_int32_t bot;
395	jit_int32_t top;
396	jit_int32_t index;
397	jit_int32_t *offsets;
398
399	bot = 0;
400	top = line->length;
401	offsets = line->offsets;
402	for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
403	if (offset < offsets[index])
404	top = index;
405	/* offset should be already verified to be in range */
406	else if (index == line->length - 1 \|\|
407	(offset >= offsets[index] && offset < offsets[index + 1]))
408	break;
409	else
410	bot = index + 1;
411	}
412
413	return (index);
414	}