![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to stp222x-asearch.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [The Machine Emulator] / tme / ic / stp22xx|
Return to stp222x-asearch.c CVS log | Up to [The Machine Emulator] / tme / ic / stp22xx |
1.1 root 1: /* $Id: stp222x-asearch.c,v 1.1 2009/02/28 16:29:25 fredette Exp $ */
2:
3: /* ic/stp222x-asearch.c - address space search routine for emulation
4: of the IOMMU of the UPA to SBus interface controller (STP2220) and
5: the UPA to PCI interface controller (STP2222): */
6:
7: /*
8: * Copyright (c) 2009 Matt Fredette
9: * All rights reserved.
10: *
11: * Redistribution and use in source and binary forms, with or without
12: * modification, are permitted provided that the following conditions
13: * are met:
14: * 1. Redistributions of source code must retain the above copyright
15: * notice, this list of conditions and the following disclaimer.
16: * 2. Redistributions in binary form must reproduce the above copyright
17: * notice, this list of conditions and the following disclaimer in the
18: * documentation and/or other materials provided with the distribution.
19: * 3. All advertising materials mentioning features or use of this software
20: * must display the following acknowledgement:
21: * This product includes software developed by Matt Fredette.
22: * 4. The name of the author may not be used to endorse or promote products
23: * derived from this software without specific prior written permission.
24: *
25: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
26: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
27: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
28: * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
29: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
30: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
31: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
33: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34: * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35: * POSSIBILITY OF SUCH DAMAGE.
36: */
37:
38: #include <tme/common.h>
39: _TME_RCSID("$Id: stp222x-asearch.c,v 1.1 2009/02/28 16:29:25 fredette Exp $");
40:
41: #include "stp222x-impl.h"
42:
43: #ifndef tme_stp222x_asearch
44:
45: #define tme_stp222x_asearch tme_stp222x_asearch32
46: #define _tme_stp222x_asearch_t tme_bus_addr32_t
47: #include "stp222x-asearch.c"
48: #undef tme_stp222x_asearch
49: #undef _tme_stp222x_asearch_t
50:
51: #define tme_stp222x_asearch tme_stp222x_asearch64
52: #define _tme_stp222x_asearch_t tme_bus_addr64_t
53: #include "stp222x-asearch.c"
54: #undef tme_stp222x_asearch
55: #undef _tme_stp222x_asearch_t
56:
57: #else /* defined(tme_stp222x_asearch) */
58:
59: /* this searches a set of address ranges for one covering the given
60: address: */
61: tme_uint32_t
62: tme_stp222x_asearch(const struct tme_stp222x_arange *aranges,
63: tme_uint32_t pivot,
64: _tme_stp222x_asearch_t address)
65: {
66: tme_uint32_t left_p1;
67: tme_uint32_t right_p1;
68: _tme_stp222x_asearch_t first;
69: _tme_stp222x_asearch_t offset;
70: _tme_stp222x_asearch_t size_m1;
71:
72: /* binary search for the address: */
73: left_p1 = 1;
74: right_p1 = pivot;
75: for (; left_p1 <= right_p1; ) {
76:
77: /* get this pivot: */
78: pivot = (left_p1 + right_p1 - 2) / 2;
79:
80: /* get the first address in the range at the pivot: */
81: first = aranges[pivot].tme_stp222x_arange_first;
82: assert (first == aranges[pivot].tme_stp222x_arange_first);
83:
84: /* if the search address is less than this first address: */
85: if (address < first) {
86:
87: /* move left: */
88: right_p1 = pivot;
89:
90: /* if we have exhausted the ranges, any insertion should happen
91: at this last pivot: */
92: }
93:
94: /* otherwise, the search address is greater than or equal to the
95: first address: */
96: else {
97:
98: /* get the offset of the search address from the first
99: address: */
100: offset = address - first;
101:
102: /* get the size, minus one, of the range at the pivot: */
103: size_m1 = aranges[pivot].tme_stp222x_arange_size_m1;
104: assert (size_m1 == aranges[pivot].tme_stp222x_arange_size_m1);
105:
106: /* if the search address is in the range at the pivot: */
107: if (offset <= size_m1) {
108: return (pivot);
109: }
110:
111: /* move right: */
112: left_p1 = pivot + 2;
113:
114: /* if we have exhausted the ranges, any insertion should happen
115: after this last pivot: */
116: pivot++;
117: }
118: }
119:
120: /* this address missed: */
121: return (TME_STP222X_ASEARCH_MISS + pivot);
122: }
123:
124: #endif /* defined(tme_stp222x_asearch) */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.