Return to stp222x-asearch.c CVS log

Up to [The Machine Emulator] / tme / ic / stp22xx

Annotation of tme/ic/stp22xx/stp222x-asearch.c, revision 1.1

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.