/*******************************************************************
  isqrt.c	                  Copyright © 1998 Virtual Paradigm   
  ----------------------------------------------------------------
  $Release  : 1.0.0 
  $Revision : 												       
	r1.00	7-11-98
                                                                   
  $Author(s):													   
		- Original by Andrew hirsh
		- Converted to MSVC++ asm by Dennis Predovnik
  
  $Purpose  : 
		Calculates an approximate sqrt value based on a LUT.
		This routine is 330% faster than the math library sqrt(). 
		Basically what it does is gets the closest integer square root 
		value of a parameter. 
		ie 
			isqrt of 16 is 4
			isqrt of 18 is 4
			isqrt of 28 is 5
			etc
  
*******************************************************************/

#include <stdio.h>
#include <math.h>



long isqrt(long nr);
void setupSqrtTable();


//---------------------------------------------------------------------
// Call this first to build LUT for isqrt routine..
//---------------------------------------------------------------------
unsigned char sqrt_tab[256];

void setupSqrtTable(){
	long  i;
	for(i=0;i<256;i++)
		sqrt_tab[i] = 256.0 * sqrt( i/256.0 );
}


//-------------------------------------------------------------------- 
// Integer sqrt  
// ============ 
//
// In :
// eax - integer value to root
//
// Out:
// eax - root ( only bits 15..0 may be ones. )
//
// - Routine converted to work with MSVC++ asm 
//   by Dennis Predovnik...  Yoooooooo, I just love asm !!!
//
//  No registers modified, no stack usage
//
//-------------------------------------------------------------------- 

long isqrt(long nr){

	__asm{
		 mov	eax,nr
         cmp    eax,10000h
         jb     c_15_0
         cmp    eax,1000000h
         jb     c_23_16

	// bit 31..24
         cmp    eax,10000000h
         jb     c_27_24
         cmp    eax,40000000h
         jb     c_29_28
         shr    eax,24
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,8
		 jmp	ende

	c_29_28: 
		 shr    eax,22
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,7
		 jmp	ende
	c_27_24: 
		 cmp    eax,4000000h
         jb     c_25_24
         shr    eax,20
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,6
		 jmp	ende
	c_25_24: 
		 shr    eax,18
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,5
		 jmp	ende

	// bit 23..16
	c_23_16: 
		 cmp    eax,100000h
         jb     c_19_16
         cmp    eax,400000h
         jb     c_21_20
         shr    eax,16
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,4
		 jmp	ende
	c_21_20: 
		 shr    eax,14
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,3
		 jmp	ende
	c_19_16: 
		 cmp    eax,40000h
         jb     c_17_16
         shr    eax,12
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,2
		 jmp	ende
	c_17_16: 
		 shr    eax,10
         mov    al, BYTE PTR [sqrt_tab+eax]
         shl    eax,1
		 jmp	ende

	c_15_0:  
		 cmp    eax,100h
         jb     c_7_0

	// bit 15..8
         cmp    eax,1000h
         jb     c_11_8
         cmp    eax,4000h
         jb     c_13_12
         shr    eax,8
         mov    al, BYTE PTR [sqrt_tab+eax]
		 jmp	ende
	c_13_12: 
		 shr    eax,6
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,1
		 jmp	ende
	c_11_8:  
		 cmp    eax,400h
         jb     c_9_8
         shr    eax,4
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,2
		 jmp	ende
	c_9_8:   
		 shr    eax,2
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,3
		 jmp	ende
	// bit 7..0
	c_7_0:   
		 cmp    eax,10h
         jb     c_3_0
         cmp    eax,40h
         jb     c_5_4
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,4
		 jmp	ende
	c_5_4:   
		 shl    eax,2
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,5
		 jmp	ende
	c_3_0:   
		 cmp    eax,4h
         jb     c_1_0
         shl    eax,4
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,6
		 jmp	ende
	c_1_0:   
		 shl    eax,6
         mov    al, BYTE PTR [sqrt_tab+eax]
         shr    eax,7

	ende:
	}

	return;          // result is in eax
}
