Skip to content

Instantly share code, notes, and snippets.

@saga
Created May 31, 2010 05:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save saga/419585 to your computer and use it in GitHub Desktop.
Save saga/419585 to your computer and use it in GitHub Desktop.
#include "stdafx.h"
#include <stdlib.h>
/* Magic numbers for the algorithm */
static const unsigned long mask01 = 0x01010101;
static const unsigned long mask80 = 0x80808080;
#define LONGPTR_MASK (sizeof(long) - 1)
/*
* Helper macro to return string length if we caught the zero
* byte.
*/
#define testbyte(x) \
do { \
if (p[x] == '\0') \
return (p - str + x); \
} while (0)
/* http://www.freebsd.org/cgi/cvsweb.cgi/src/lib/libc/string/strlen.c?rev=1.10 */
inline size_t strlenBSD(const char *str)
{
const char *p;
const unsigned long *lp;
long va, vb;
/*
* Before trying the hard (unaligned byte-by-byte access) way
* to figure out whether there is a nul character, try to see
* if there is a nul character is within this accessible word
* first.
*
* p and (p & ~LONGPTR_MASK) must be equally accessible since
* they always fall in the same memory page, as long as page
* boundaries is integral multiple of word size.
*/
lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
va = (*lp - mask01);
vb = ((~*lp) & mask80);
lp++;
if (va & vb)
/* Check if we have \0 in the first part */
for (p = str; p < (const char *)lp; p++)
if (*p == '\0')
return (p - str);
/* Scan the rest of the string using word sized operation */
for (; ; lp++) {
va = (*lp - mask01);
vb = ((~*lp) & mask80);
if (va & vb) {
p = (const char *)(lp);
if (p[0] == '\0')
return (p - str + 0);
if (p[1] == '\0')
return (p - str + 1);
if (p[2] == '\0')
return (p - str + 2);
if (p[3] == '\0')
return (p - str + 3);
}
}
/* NOTREACHED */
return (0);
}
inline size_t strlenBSD2(const char *str)
{
const char *p;
const unsigned long *lp;
long va, vb;
/*
* Before trying the hard (unaligned byte-by-byte access) way
* to figure out whether there is a nul character, try to see
* if there is a nul character is within this accessible word
* first.
*
* p and (p & ~LONGPTR_MASK) must be equally accessible since
* they always fall in the same memory page, as long as page
* boundaries is integral multiple of word size.
*/
lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
va = (*lp - mask01);
vb = ((~*lp) & mask80);
lp++;
if (va & vb)
/* Check if we have \0 in the first part */
for (p = str; p < (const char *)lp; p++)
if (*p == '\0')
return (p - str);
/* Scan the rest of the string using word sized operation */
for (; ; lp++) {
va = (*lp - mask01);
vb = ((~*lp) & mask80);
if (va & vb) {
p = (const char *)(lp);
testbyte(0);
testbyte(1);
testbyte(2);
testbyte(3);
}
}
/* NOTREACHED */
return (0);
}
inline int strlenVC(const char* string)
{
__asm
{
mov ecx, string ; ecx -> string
test ecx,3 ; test if string is aligned on 32 bits
je short main_loop
str_misaligned:
; simple byte loop until string is aligned
mov al,byte ptr [ecx]
add ecx,1
test al,al
je short byte_3
test ecx,3
jne short str_misaligned
add eax,dword ptr 0 ; 5 byte nop to align label below
align 16 ; should be redundant
main_loop:
mov eax,dword ptr [ecx] ; read 4 bytes
mov edx,7efefeffh
add edx,eax
xor eax,-1
xor eax,edx
add ecx,4
test eax,81010100h
je short main_loop
; found zero byte in the loop
mov eax,[ecx - 4]
test al,al ; is it byte 0
je short byte_0
test ah,ah ; is it byte 1
je short byte_1
test eax,00ff0000h ; is it byte 2
je short byte_2
test eax,0ff000000h ; is it byte 3
je short byte_3
jmp short main_loop ; taken if bits 24-30 are clear and bit
; 31 is set
byte_3:
lea eax,[ecx - 1]
mov ecx,string
sub eax,ecx
jmp ReturnLabel
byte_2:
lea eax,[ecx - 2]
mov ecx,string
sub eax,ecx
jmp ReturnLabel
byte_1:
lea eax,[ecx - 3]
mov ecx,string
sub eax,ecx
jmp ReturnLabel
byte_0:
lea eax,[ecx - 4]
mov ecx,string
sub eax,ecx
jmp ReturnLabel
}
ReturnLabel:
;
}
typedef unsigned int word_t;
static word_t const magic = (word_t)(0x0101010101010101ull);
inline size_t strlenDiet(const char *s)
{
const char *t = s;
word_t word;
word_t mask;
/* Byte compare up until word boundary */
for (; ((unsigned long) t & (sizeof(magic)-1)); t++)
if (!*t) return t - s;
/* Word compare */
do {
word = *((word_t const *) t); t += sizeof word;
word = (word - magic) &~ word;
word &= (magic << 7);
} while (word == 0);
/* word & 0x80808080 == word */
word = (word - 1) & (magic << 10);
word += (word << 8) + (word << 16);
t += word >> 26;
return t - sizeof(word) - s;
}
inline size_t strlenStandard(const char * str)
{
const char *s;
for (s = str; *s; ++s);
return(s - str);
}
TCHAR bufferWill[512];
#include <vector>
using namespace std;
#include "logger.h"
int _tmain(int argc, _TCHAR* argv[])
{
CLogFile logger("c:\\log.txt");
// 1)
FILE* pf = fopen("c:\\WindowsUpdate.log", "r");
vector<char*> vecBuf;
vector<char*> vecBuf2;
vector<char*> vecBuf3;
for (int i=0; i< 300000; i++)
{
char* p = (char*)malloc(sizeof p * 1000);
if (fgets(p, 990, pf))
{
vecBuf.push_back(p);
vecBuf2.push_back(p+1);
vecBuf3.push_back(p+2);
}
}
CPerfTimer timer1;
timer1.Start();
Sleep(100);
timer1.Stop();
timer1.Start();
for (int i=0; i< vecBuf.size(); i++)
{
int len = strlenVC(vecBuf[i]);
}
timer1.Stop();
double timeVC = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenVC %f ##\n"),
timeVC);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf.size(); i++)
{
int len = strlenDiet(vecBuf[i]);
}
timer1.Stop();
double timeDiet = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenDiet %f ##\n"),
timeDiet);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf.size(); i++)
{
int len = strlenStandard(vecBuf[i]);
}
timer1.Stop();
double timeStandard = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenStandard %f ##\n"),
timeStandard);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf.size(); i++)
{
int len = strlen(vecBuf[i]);
}
timer1.Stop();
double timeA = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlen %f ##\n"),
timeA);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf.size(); i++)
{
int len = strlenBSD(vecBuf[i]);
}
timer1.Stop();
double timeAbsd = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenBSD %f ##\n"),
timeAbsd);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf.size(); i++)
{
int len = strlenBSD2(vecBuf[i]);
}
timer1.Stop();
double timeA3 = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenBSD2 %f ##\n"),
timeA3);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf2.size(); i++)
{
int len = strlenVC(vecBuf2[i]);
}
timer1.Stop();
double timeVC2 = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenVC %f ##\n"),
timeVC2);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf2.size(); i++)
{
int len = strlenDiet(vecBuf2[i]);
}
timer1.Stop();
double timeDiet2 = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenDiet %f ##\n"),
timeDiet2);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf2.size(); i++)
{
int len = strlenStandard(vecBuf2[i]);
}
timer1.Stop();
double timeStandard2 = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenStandard %f ##\n"),
timeStandard2);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf2.size(); i++)
{
int len = strlen(vecBuf2[i]);
}
timer1.Stop();
double timeAst = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlen %f ##\n"),
timeAst);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf2.size(); i++)
{
int len = strlenBSD(vecBuf2[i]);
}
timer1.Stop();
double timeA22 = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenBSD %f ##\n"),
timeA22);
logger.WriteStr(bufferWill);
// **********************************************
timer1.Start();
for (int i=0; i< vecBuf2.size(); i++)
{
int len = strlenBSD2(vecBuf2[i]);
}
timer1.Stop();
double timeA32 = timer1.Elapsedus();
// *********************william test*************
_stprintf(bufferWill, TEXT(" Result strlenBSD2 %f ##\n"),
timeA32);
logger.WriteStr(bufferWill);
// **********************************************
for (int i=0; i< vecBuf.size(); i++)
{
free (vecBuf[i]);
}
fclose(pf);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment