1*50caa7fdSmiod/* $OpenBSD: ffs.S,v 1.10 2023/01/13 17:52:08 miod Exp $ */ 248f0b646Sjsg 311096442Sart/* 411096442Sart * Copyright (c) 1992, 1993 511096442Sart * The Regents of the University of California. All rights reserved. 611096442Sart * 711096442Sart * This software was developed by the Computer Systems Engineering group 811096442Sart * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 911096442Sart * contributed to Berkeley. 1011096442Sart * 1111096442Sart * Redistribution and use in source and binary forms, with or without 1211096442Sart * modification, are permitted provided that the following conditions 1311096442Sart * are met: 1411096442Sart * 1. Redistributions of source code must retain the above copyright 1511096442Sart * notice, this list of conditions and the following disclaimer. 1611096442Sart * 2. Redistributions in binary form must reproduce the above copyright 1711096442Sart * notice, this list of conditions and the following disclaimer in the 1811096442Sart * documentation and/or other materials provided with the distribution. 196580fee3Smillert * 3. Neither the name of the University nor the names of its contributors 2011096442Sart * may be used to endorse or promote products derived from this software 2111096442Sart * without specific prior written permission. 2211096442Sart * 2311096442Sart * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2411096442Sart * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2511096442Sart * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2611096442Sart * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2711096442Sart * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2811096442Sart * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2911096442Sart * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3011096442Sart * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3111096442Sart * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3211096442Sart * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3311096442Sart * SUCH DAMAGE. 3411096442Sart */ 3511096442Sart 369b9d2a55Sguenther#include "SYS.h" 3711096442Sart/* 3811096442Sart * ffs returns the number of the rightmost bit set in its argument, 3911096442Sart * i.e., the lowest value such that (x & (ffs(x) - 1)) is nonzero. 4011096442Sart * If no bits are set, ffs returns 0. 4111096442Sart * 4211096442Sart * We use a table lookup on each byte. 4311096442Sart * 4411096442Sart * In each section below, %o1 is the current byte (0, 1, 2, or 3). 4511096442Sart * The last byte is handled specially: for the first three, 4611096442Sart * if that byte is nonzero, we return the table value 4711096442Sart * (plus 0, 8, or 16 for the byte number), but for the last 4811096442Sart * one, we just return the table value plus 24. This means 4911096442Sart * that ffstab[0] must be -24 so that ffs(0) will return 0. 5011096442Sart */ 5111096442SartENTRY(ffs) 5232b97dedSpascal#ifdef __PIC__ 53*50caa7fdSmiod PIC_PROLOGUE(%o5, %o4) 54*50caa7fdSmiod set __ffstab, %o4 55*50caa7fdSmiod ldx [%o5 + %o4], %o2 5611096442Sart#else 5781621933Sguenther set __ffstab, %o2 5811096442Sart#endif 5911096442Sart andcc %o0, 0xff, %o1 ! get low byte 6011096442Sart be,a 1f ! try again if 0 6111096442Sart srl %o0, 8, %o0 ! delay slot, get ready for next byte 6211096442Sart 6311096442Sart retl ! return ffstab[%o1] 6411096442Sart ldsb [%o2 + %o1], %o0 6511096442Sart 6611096442Sart1: 6711096442Sart andcc %o0, 0xff, %o1 ! byte 1 like byte 0... 6811096442Sart be,a 2f 6911096442Sart srl %o0, 8, %o0 ! (use delay to prepare for byte 2) 7011096442Sart 7111096442Sart ldsb [%o2 + %o1], %o0 7211096442Sart retl ! return ffstab[%o1] + 8 7311096442Sart add %o0, 8, %o0 7411096442Sart 7511096442Sart2: 7611096442Sart andcc %o0, 0xff, %o1 7711096442Sart be,a 3f 7811096442Sart srl %o0, 8, %o0 ! (prepare for byte 3) 7911096442Sart 8011096442Sart ldsb [%o2 + %o1], %o0 8111096442Sart retl ! return ffstab[%o1] + 16 8211096442Sart add %o0, 16, %o0 8311096442Sart 8411096442Sart3: ! just return ffstab[%o0] + 24 8511096442Sart ldsb [%o2 + %o0], %o0 8611096442Sart retl 8711096442Sart add %o0, 24, %o0 88ae3cb403SguentherEND(ffs) 89ae3cb403Sguenther.protected ffs 9011096442Sart 91*50caa7fdSmiod .section .rodata 9281621933Sguenther__ffstab: 9311096442Sart .byte -24,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 00-0f */ 9411096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 10-1f */ 9511096442Sart .byte 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 20-2f */ 9611096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 30-3f */ 9711096442Sart .byte 7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 40-4f */ 9811096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 50-5f */ 9911096442Sart .byte 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 60-6f */ 10011096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 70-7f */ 10111096442Sart .byte 8,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 80-8f */ 10211096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 10-9f */ 10311096442Sart .byte 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* a0-af */ 10411096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* b0-bf */ 10511096442Sart .byte 7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* c0-cf */ 10611096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* d0-df */ 10711096442Sart .byte 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* e0-ef */ 10811096442Sart .byte 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* f0-ff */ 109