Binary Search for Highest Bit Position, 130 | HP UX Developer Tools

Programming Examples

1. Binary Search for Highest Bit Position

1. Binary Search for Highest Bit Position

The Shift Double and Extract Unsigned instructions are used to implement a binary search. Bits shifted into general register 0 are effectively discarded.

.CODE

.EXPORT post

;

;This procedure calculates the highest bit position

;set in the word passed in as the first argument.

;If passed parameter is non-zero, the algorithm

;starts by assuming it is one.

;A binary search for a set bit is then used

;to enhance performance.

;

;The calculated bit position is returned to the caller.

.PROC

post

.CALLINFO SAVE_RP

.ENTER

COMB,=,N	%r0,%arg0,all_zeros	;	No bits set
LDI	31,%ret0	;	assume 2 to the 0 power

;

;if extracted bits non-zero, fall thru to change assumption

;else set up 16 low order bits and keep assumption

;

EXTRU,<>	%arg0,15,16,%r0	; check 16	high order bits
SHD,TR	%arg0,%r0,16,%arg0	; left shift arg0		16	bits
ADDI	-16,%ret0,%ret0	; assume 2	to the	16	power

;

;if extracted bits non-zero, fall thru to change assumption

;else set up 8 low order bits and keep assumption

;

EXTRU,<>	%arg0,7,8,%r0	; check next 8 high		order bits
SHD,TR	%arg0,%r0,24,%arg0	; left shift arg0	8	bits
ADDI	-8,%ret0,%ret0	; assume 8 higher	power of 2

;

;if extracted bits non-zero, fall thru to change assumption

;else set up 4 low order bits and keep assumption

;

EXTRU,<>	%arg0,3,4,%r0	; check next 4 high		order bits
SHD,TR	%arg0,%r0,28,%arg0	; left shift arg0	4	bits
ADDI	-4,%ret0,%ret0	; assume 4 higher	power of 2

;

;if extracted bits non-zero, fall thru to change assumption

;else set up 2 low order bits and keep assumption

;

EXTRU,<>	%arg0,1,2,%r0	; check next 2 high		order bits
SHD,TR	%arg0,%r0,30,%arg0	; left shift arg0	2	bits
ADDI	-2,%ret0,%ret0	; assume 2 higher	power of 2

130

Chapter 7

Image 130

HP UX Developer Tools manual Binary Search for Highest Bit Position, 130

Contents

HP 9000 Computers 92432-90012 June Restricted Rights Legend Legal NoticesHanover Street Palo Alto, California Contents Assembler Directives and Pseudo-Operations Contents Contents Contents Contents Pseudo-Instruction Set Assembling Your Program Programming Examples Diagnostic MessagesIndex Printing History PrefaceEdition Date Software Version Audience Related Documentation Typographical Conventions This Manual Summary of Technical Changes for HP-UX Assembly Language Assembler Features Assembler Features Summary of Changes for PA-RISC Summary of Changes for PA-RISCSummary of Changes for PA-RISC 2.0W Wide Mode, 64-bit Chapter Summary of Changes for PA-RISC 2.0W Wide Mode, 64-bit Program Structure Program Structure Label Opcode Operands Comments Symbols and Constants Symbols and Constants Integer Constants Signed Unsigned Registers and Register Mnemonics Registers and Register Mnemonics Registers by using an L or R sufﬁx General Registers Single-Precision Floating-Point Registers Space Registers Double-Precision Floating-Point RegistersControl Registers Synonyms Register Procedure Calling Conventions Register Synonyms Description Standard Arithmetic Operators ExpressionsExpressions Operator Operation Legal Combinations For Relocatable Terms Operation Result Available Field Selectors Meaning Field Meaning Selector Multiple of 2048 allows a three-instruction sequence Parenthesized Subexpressions Operands and Completers Operands and Completers Addi Deﬁning New Instructions With Macros Macro ProcessingMacro Processing Contains general register 19, or binary 10011. These HP-UX Architecture Conventions Spaces Spaces Memory Layout on HP-UX Sr4 Sr5 Sr6 Attributes SubspacesSubspaces Standard Subspaces and Sort Keys DirectivesSpace Subspace Sort Key Use Sections in 64-bit Mode Sections in 64-bit Mode $INIT$ Location Counters Location Counters Compiler Conventions Compiler Conventions Compiler Conventions Global Symbol Usage Mfctl Shared Libraries Assembly ListingShared Libraries Assembly Listing Assembler Directives IntroductionDirective Function Requests common storage for a speciﬁed number Bytes Pseudo-Operations Directive Function Reserves 16 bits a half word of storage Parameters Align DirectiveSyntax Example Discussion Allow DirectiveAllow Directive To the .LEVEL speciﬁed for the ﬁle Block and .BLOCKZ Pseudo-Operations Block and .BLOCKZ Pseudo-Operations Space $TEXT$ Subspa $CODE$ Block Byte Pseudo-Operation Byte Pseudo-OperationByte initvalue , initvalue Call Directive Call DirectiveCall argumentdescription argumentdescription ﬁrst word in the argument list Form of argument-description is Arg=location Where arg canReturn value for a procedure Second word in the argument list LIT Align Word Procend Export Callinfo Directive Callinfo DirectiveCallinfo parameter , parameter Register ENTRYSR= Unwound It restores the RP value when it encounters a .LEAVE Callinfo Directive Stack Frames Re-enter code subspace Label .COMM numbytes Comm DirectiveComm Directive Label Labels the location of the reserved storage Copyright Directive Copyright DirectiveCompany-name Proc Callinfo Enter Double Pseudo-Operation Integer .fraction E powerFraction E power Double Pseudo-Operation Dword Pseudo-Operation Dword Pseudo-OperationDword initvalue , initvalue END Directive END Directive Endm Directive Endm Directive Enter and .LEAVE Pseudo-Operations Enter and .LEAVE Pseudo-Operations Space $TEXT$ Entry and .EXIT Directives Entry and .EXIT Directives EQU Directive Symbolicname .EQU valueEQU Directive Value Export Directive Export Directive Argument Export proc,ENTRY,ARGW0=GR Float Pseudo-Operation Float Pseudo-Operation Half Pseudo-Operation Half Pseudo-OperationHalf initvalue , initvalue Import Directive Import Directive NOP END Label labelid Label DirectiveLabel Directive Labelid Names the label identiﬁer Level Directive Level Directive Level Directive Listoff and .LISTON Directives Listoff and .LISTON Directives Liston Code Space $TEXT$ SPNUM=0,SORT=0 Subspa $CODE$ Locct Directive Locct Directive Macro Directive Macro DirectiveLabel .MACRO formalparameter,formalparameter Examples 100 Origin Directive Origin DirectiveChapter 101 Proc and .PROCEND Directives Proc and .PROCEND Directives102 Chapter 103 Label .REG typedregister REG DirectiveREG Directive Label User-deﬁned register name Shlibversion Directive Shlibversion DirectiveChapter 105 Space Directive Space Directive106 Chapter 107 Spnum Pseudo-Operation Spnum Pseudo-Operation108 String and .STRINGZ Pseudo-Operations String and .STRINGZ Pseudo-OperationsChapter 109 110 Name An identiﬁer that names the current subspace Subspa DirectiveSubspa Directive Chapter 111 112 Chapter 113 Version Directive Version Directive114 Word initvalue , initvalue Word Pseudo-OperationWord Pseudo-Operation Chapter 115 Programming Aids Directive Space Name Default ParametersProgramming Aids Predeﬁned Subspace Directives Shortdata Chapter 117 Programming Aids 118 Pseudo-Instruction Set 119 120 Cond Description Compare and Branch Conditions Comb and ComibChapter 121 Add and Branch Conditions Addb and Addib Description 122 Invoking the Assembler 123 Assemble code for the architecture Using the as CommandUsing the as Command 124 Level ﬁlenameChapter 125 Online User Guide WnumberTables, see HP-UX Linker and Libraries 126 Passing Arguments to the Assembler Using the cc CommandUsing the cc Command Wa, ,as-argument as-argument Cpp Preprocessor 128 Programming Examples 129 Binary Search for Highest Bit Position Binary Search for Highest Bit Position130 Chapter 131 Copying a String Copying a String132 Chapter 133 Dividing a Double-Word Dividend Dividing a Double-Word Dividend134 Programming Examples Chapter 135 Program Listing Demonstrating the Procedure Calling ConventionDemonstrating the Procedure Calling Convention 136 Assembly Program Listing Chapter 137 Output of the cc -S Command Output of the cc -S CommandAssembly Program Listing From the C Compiler 138 Chapter 139 Output of the cc -S Command 140 141 Option operand 142 Chapter 143 Reserve 144 Use a general register Wrong register type usedChapter 145 Use a control register Use a space register146 Chapter 147 148 Chapter 149 150 Chapter 151 Used to invoke the assembler 152 Chapter 153 Error Messages Error Messages154 Chapter 155 156 Chapter 157 158 1029 10271028 1030 1033 10311032 1034 1037 10351036 1038 162 Chapter 163 1056 10541055 1057 Chapter 165 166 Chapter 167 168 1081 Format keyword=value1080 1082 170 1090 10881089 Chapter 171 1095 10911094 1096 1099 10971098 1100 1103 11011102 1104 1105 Chapter 175 Panic Messages Panic Messages176 2007 20052006 2008 User Warning Messages User Warning Messages178 7005 70037004 7006 180 Chapter 181 182 7200 Limit Error MessagesLimit Error Messages 7201 7204 72027203 184 Diagnostic Messages Chapter 185 186 Branching Error Messages Branching Error MessagesChapter 187 188 Chapter 189 190 Chapter 191 192 7834 78277828 7835 Expr 78367837 194 Index Index 195 196 Numerics Index 197 Copyright 198 HP C/HP-UX,49 Index 199 Mfctl 200 Double Index 201 See also memory 202