ATOI + ITOA remake

Iniciado por 85, 22 Febrero 2013, 03:32 AM

0 Miembros y 1 Visitante están viendo este tema.

85

EDITADO
SE AGREGARON VERSIONES MEJORADAS PARA NO HACER USO DE TABLAS, NI DE FUNCIONES INNECESARIAS COMO LOG, POW, STRLEN, de CTYPE, de STRING, etc
SIN ASIGNACIONES DINÁMICAS, y USANDO MACROS PARA HACER EL CÓDIGO MÁS LEGIBLE..

//////////////////

Estaba repasando un poco cómo había hecho las implementaciones personales de estas funciones,
http://foro.elhacker.net/programacion_cc/atoi_itoa_personalizadas-t358459.0.html;msg1734670#msg1734670

..pero antes de hacer una implementación lo primero es saber como funciona realmente la original.. en base a esto es que decidí arreglar estas funciones siguiendo la misma lógica de construcción, que por cierto es una que suelo usar seguido.

Empezando por ATOI
Código (cpp) [Seleccionar]

/********************************************************************************************************

// By 85
// boyscout_arg@hotmail.com
// etalking.com.ar
// David Riedel
// 2013

*********************************************************************************************************/

#pragma warning (disable:4305)
#pragma warning (disable:4309)
#pragma warning (disable:4244)
#pragma warning (disable:4018)
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>

/////

// Sin necesidad de llamadas innecesarias a funciones de CTYPE, MATH, STRING, etc
// Sin necesidad de Tablas, solo un array con los números enteros que tampoco es necesario
// pero no hace la gran diferencia ;-D

//////////////////////////////////////////////////

//Se requiere pasar una cadena terminada en CERO!.
//Si no se le pasa una cadena terminada en CERO, la función va a buscar el
//primer 0 que encuentre y puede terminar en una sección de memoria contigua
//que no pertenece a la cadena pasada como parámetro.
int mi_atoi(const char* str)//Respetar el tipo de parámetro (Sólo cadenas)
{
int len, ocurrencias =0, sig=0;
for(len=0; str[len]; len++);
for(int a=0; a<len;a++) if((str[a]>=48&&str[a]<=57)) ocurrencias++;
if(ocurrencias==0) return 0;
if((sig=str[0]=='+')||(sig=str[0]=='-')) ocurrencias+=1;
if(ocurrencias<len) return 0;//Casos "11f" son 0
if(len==1) return str[0]-'0';
int ac=0, v1, cifras = len,m = 1;
for(int x=0;x<((cifras-1)-sig);x++) m*=10;
for(int i=sig;i<cifras;i++){//Factoriza y acumula
v1=str[i]-'0';
v1*=m;
ac+=v1;
m/=10;
}
if(str[0]=='-') ac*=-1;
return ac;
}

////////////////////

int main(){

// char str = 'B';
// int entero = mi_atoi(&str);

// char* str = "asdasd\0";
// int entero = mi_atoi(str);

// char* str = "8a3\0";
// int entero = mi_atoi(str);

// char* str = "83312321\0";
// int entero = mi_atoi(str);

// char* str = "000000099\0";
// int entero = mi_atoi(str);

// char* str = "9\0";
// int entero = mi_atoi(str);

// char* str = "20\0";
// int entero = mi_atoi(str);

// char* str = "500\0";
// int entero = mi_atoi(str);

// char* str = "+500\0";
// int entero = mi_atoi(str);

// char* str = "0500\0";
// int entero = mi_atoi(str);

// char* str = "0\0";
// int entero = mi_atoi(str);

// char* str = "10f\0";
// int entero = mi_atoi(str);

// char* str = "01ff\0";
// int entero = mi_atoi(str);

// char* str = "0f\0";
// int entero = mi_atoi(str);

// char* str = "+12\0";
// int entero = mi_atoi(str);

// char* str = "+12\0";
// int entero = mi_atoi(str);

// char* str = "03232\0";
// int entero = mi_atoi(str);

// printf("%d", entero);


printf("%d\n",mi_atoi("-110"));
printf("%d\n",mi_atoi("-10"));
printf("%d\n",mi_atoi("0"));
printf("%d\n",mi_atoi("1"));
printf("%d\n",mi_atoi("-1"));
printf("%d\n",mi_atoi("-11"));
printf("%d\n",mi_atoi("-2"));
printf("%d\n",mi_atoi("-200"));
printf("%d\n",mi_atoi("-220"));
printf("%d\n",mi_atoi("+0"));
printf("%d\n",mi_atoi("-0"));
printf("%d\n",mi_atoi("+1"));
printf("%d\n",mi_atoi("+33"));
printf("%d\n",mi_atoi("-330"));
printf("%d\n",mi_atoi("-3000"));
// printf("%d\n",mi_atoi("-1"));
// printf("%d\n",mi_atoi("-200"));
// printf("%d\n",mi_atoi("-220"));
printf("%d\n",mi_atoi("+12"));

printf("\n");
system("pause");
return 0;
}


El problema que enfrenta esta función es cuando alguien trata de pasarle un parámetro que no es una cadena, por ejemplo un 'char'


char str = 'B';
int entero = mi_atoi(&str);


se lo hace de esa forma especificando la dirección de la variable, pero en la función original ATOI esto devuelve 0, según mis pruebas.

y al respecto revisaba también unos post en los cuales se hablaba acerca de la utilidad del operador ternario, como se puede observar son muy útiles para usarlos como índices en matrices y vectores.

http://foro.elhacker.net/programacion_cc/calcular_el_maximo_usando_operador-t383707.0.html
http://foro.elhacker.net/programacion_cc/aporte_operador_condicional-t383420.0.html


int tab1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
val1 =  tab1[(str[i]=='0' ? 9:(((int)str[i]-48)-1))];


para los principiantes les explico que la evaluación que se hace es que si el caractér es 0 se procede a usar el número 9 como índice, de otra forma se usa otro índice..

Bueno y la implementación de ITOA es esta:
Código (cpp) [Seleccionar]

/********************************************************************************************************

// By 85
// boyscout_arg@hotmail.com
// etalking.com.ar
// David Riedel
// 2013

*********************************************************************************************************/

#pragma warning (disable:4305)
#pragma warning (disable:4309)
#pragma warning (disable:4244)
#pragma warning (disable:4018)
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>

/////

// Sin necesidad de llamadas innecesarias a funciones de CTYPE, MATH, STRING, etc
// Sin necesidad de Tablas, sólo un array con los números enteros que tampoco es necesario
// pero no hace la gran diferencia ;-D

//////////////////////////////////////////////////

char* mi_itoa(int num, char* str)
{
int sig = -1;
if(num<0){
num*=-1;
if(num<10){
str[0]='-'; str[1]='0'+num; str[2]=0; return str;
} else {
sig=1;
}
}
else if(num==0){
str[0]='0'; str[1]=0; return str;
} else {
if(num<10){
str[0]='0'+num; str[1]=0; return str;
} else {
sig=0;
}
}
if(sig!=-1){
int copia= num, m = 1, cifras = 1;
for(;copia>=10;copia/=10) cifras++;
for(int x=0;x<(cifras-1);x++) m*=10;
float v1=num;
int v2=0, v3=num;
if(sig) str[0]='-';
for(int i=0; i<cifras; i++){//Descompone en factores
v1/=m;
v2=(int)v1*m;
v3-=v2;
m/=10;
str[i+sig]=48+(int)v1;
v1=v3;
}
str[i+sig]=0;//Si str está a 0 no es necesario..
}
return str;
}

///////////////////

int main(){


char str[256];

// mi_itoa(321312,str);
// printf(str);

// itoa(02321,str,10);
// printf(str);

// mi_itoa(02321,str);
// printf(str);

// mi_itoa(-12321,str);
// printf(str);

// itoa(-012321,str,10);
// printf(str);

// mi_itoa(-012321,str,10);
// printf(str);

// mi_itoa(555,str);
// printf(str);

// mi_itoa(0,str);
// printf(str);

// mi_itoa(1,str);
// printf(str);

// mi_itoa(500,str);
// printf(str);

printf(mi_itoa(+321312,str));printf("\n");
printf(mi_itoa(-321312,str));printf("\n");
printf(mi_itoa(321312,str));printf("\n");
printf(mi_itoa(+0,str));printf("\n");
printf(mi_itoa(0,str));printf("\n");
printf(mi_itoa(-0,str));printf("\n");
printf(mi_itoa(+1,str));printf("\n");
printf(mi_itoa(1,str));printf("\n");
printf(mi_itoa(-1,str));printf("\n");
printf(mi_itoa(10,str));printf("\n");
printf(mi_itoa(+10,str));printf("\n");
printf(mi_itoa(-10,str));printf("\n");
printf(mi_itoa(-110,str));printf("\n");
printf(mi_itoa(-100,str));printf("\n");

printf(mi_itoa(-5000,str));printf("\n");
printf(mi_itoa(-55555,str));printf("\n");
printf(mi_itoa(550,str));printf("\n");
printf(mi_itoa(500,str));printf("\n");
printf(mi_itoa(+330,str));printf("\n");

printf(mi_itoa(-000,str));printf("\n");
printf(mi_itoa(+000,str));printf("\n");
// printf(mi_itoa(+00009,str));printf("\n");
printf(mi_itoa(+109,str));printf("\n");
printf(mi_itoa(-109,str));printf("\n");
// printf(mi_itoa(-09,str));printf("\n");
// printf(mi_itoa(+09,str));printf("\n");
printf(mi_itoa(-999,str));printf("\n");
// printf(mi_itoa(-00000999,str));printf("\n");

printf("\n");
system("pause");
return 0;
}

/////



cualquier problema diganme, sólo trataba de crear un par de funciones que funcionen tal cual las originales, y usando la misma lógica que venía usando.

les dejo el proyecto en MSVC++ 6 ya que es el compilador que tengo para esta clase de minipruebas, tengo el 2010 también..

http://www.mediafire.com/?wbscy4bu2vrq273
Me cerraron el Windows Live Spaces, entonces me creé un WordPress XD
http://etkboyscout.wordpress.com/

rir3760

Cita de: 85 en 22 Febrero 2013, 03:32 AMEl problema que enfrenta esta función es cuando alguien trata de pasarle un parámetro que no es una cadena, por ejemplo un 'char'
char str = 'B';
int entero = mi_atoi(&str);
La función atoi no puede conocer a prior si se pasa la dirección de una cadena o un carácter, esta literalmente confía en que sera usada correctamente. En otras palabras no tienes que preocuparte ya que eso es responsabilidad de quien llama a tu función.

Cita de: 85 en 22 Febrero 2013, 03:32 AM
se lo hace de esa forma especificando la dirección de la variable, pero en la función original ATOI esto devuelve 0, según mis pruebas.
El comportamiento de atoi es el siguiente:
1) Se descarta el espacio blanco.
2) Se procesa el signo.
3) Se procesan los dígitos hasta encontrar un carácter no valido.

Si por lo menos se procesa un dígito se retorna el numero, caso contrario la función debe retornar cero. No es lo ideal ya que ante una cadena como "123JKL" la función retorna 123 pero bueno, esa es su especificación.

----

En tus funciones no es necesario utilizar tablas. Para obtener el entero o carácter correspondiente solo debes sumar (o restar, dependiendo del caso) el valor '0':
'0' + Digito == '0', '1', '2', ... /* Digito == 0, 1, 2, ... */
Caracter - '0' == 0, 1, 2, ... /* Caracter == '0', '1', '2', ...*/


----

Una implementación de la función atoi con el comportamiento indicado:
#include <ctype.h>

int fn_atoi(const char *p)
{
   int num = 0;
   int sign = 1;
   
   while (isspace(*p))
      p++;
   
   if (*p == '-'){
      sign = -1;
      p++;
   }else if (*p == '+')
      p++;
   
   while (isdigit(*p)){
      num = num * 10 + *p - '0';
      p++;
   }
   
   return sign * num;
}


Y una implementación de itoa (que por cierto no es parte de la biblioteca estándar de C) es:
#include <math.h>

char *fn_itoa(int num, char *str)
{
   char *p = str + 1;
   
   if (num < 0){
      *str = '-';
      num = -num;
      p++;
   }
   
   if (num >= 10)
      p += (int) log10(num);
   
   *p = '\0';
   do {
     *--p = '0' + num % 10;
   }while ((num /= 10) > 0);
   
   return str;
}


Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

85

Aún se puede cambiar las CTYPE por algo como
Citar>=48&&<=57
, evitaríamos código extra

la tabla no es realmente necesaria es cierto, viene quedando de anteriores versiones; me gusta la ITOA como quedó

Saludos
Me cerraron el Windows Live Spaces, entonces me creé un WordPress XD
http://etkboyscout.wordpress.com/

rir3760

Cita de: 85 en 24 Febrero 2013, 00:19 AMAún se puede cambiar las CTYPE por algo como
Citar>=48&&<=57
, evitaríamos código extra
No porque sin un motivo de peso se afectaría la claridad en el código fuente. En la misma linea mejor evitar el uso de 48 y 57 sustituyendo estos por '0' y '9', el valor es el mismo con la ventaja de indicar el contexto (proceso de caracteres).

Casi lo olvido, bucles como este:
int copia = num;
int unidades_decimales = 1;// unidad de 1
while(1)
{
if(copia>=10)
{
copia /= 10;
unidades_decimales++;
}
else
{
break;
}
}

Los puedes reducir a:
int unidades_decimales = 1;
int copia;
for (copia = num; copia >= 10; copia /= 10)
   unidades_decimales++;


Por ultimo, ¿Estas aprendiendo C en base a un buen libro? Si todavía no tienes uno de calidad te recomiendo "The C Programming Language" o bien "Pointers on C", puedes obtener mas información sobre ellos mediante el motor de búsqueda de los foros.

Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

85

#4
EDITADO: Discusión no objetiva

Amigo te cuento algo,

esto:
Citar>=48&&<=57


SI, lo deberías usar ya que te vuelvo a decir SI es necesario si te gusta optimizar las cosas.
no es necesario que hagás un salto a una rutina en otra parte para ejecutar un código innecesario,
sabiendo que comparando algo directamente así:

Pseudocódigo
Citar
if(>=48&&<=57);
else NO ES UN ESPACIO NI CUALQUIER OTRA COSA SINO SÓLO NÚMEROS


Esto:

while(1)
{
if(copia>=10)
{
copia /= 10;
unidades_decimales++;
}
else
{
break;
}
}


Y esto:

int unidades_decimales = 1;
int copia;
for (copia = num; copia >= 10; copia /= 10)
  unidades_decimales++;


es lo mismo al traducirse a ASM ya que lo que vos plantéas es un cambio al nivel de TEXTO en el código humanizado o de alto nivel (C). Prestá atención que realizan las mismas operaciones y sino lo hicieran, termina siendo lo mismo porque el compilador te cuento que optimiza el código automáticamente, a lo máximo tal REDUCCiÓN termina siendo algo así como un par de instrucciones insignificantes:


push
push
call
.......
push ebp
mov ebp, esp

mov esp, ebp
pop ebp
retn

add esp, 0x8

y asumiento que no cambiás la convención de llamada a __stdcall o __fastcall, en cuyo caso la pila se limpia automáticamente por el código que hace la llamada (callee)
Me cerraron el Windows Live Spaces, entonces me creé un WordPress XD
http://etkboyscout.wordpress.com/

0xDani

@85, te estas equivocando, @rir3760 solo pretende ayudar, ha sido respetuoso y si que ha optimizado bastante tus codigos. Que te parezca que son mas dificiles de entender para una persona solo demuestra que te da mil vueltas codeando.

Si no puedes aceptar que mejoren un aporte que has hecho de forma constructiva, no se porque lo publicas.
I keep searching for something that I never seem to find, but maybe I won't, because I left it all behind!

I code for $$$
Hago trabajos en C/C++
Contactar por PM

Eternal Idol

¿En que mensaje rir3760 menciono el termino optimizar? En ninguno. ¿Verdad? Eso lo dice todo 85, mejor revee tu postura, tu reaccion estuvo fuera de lugar y deberias agradecer por los datos concretos que te aportaron (vease que uno debe respetar el tipo de los parametros que se le pasan a una funcion).
La economía nunca ha sido libre: o la controla el Estado en beneficio del Pueblo o lo hacen los grandes consorcios en perjuicio de éste.
Juan Domingo Perón

85

#7

EDITADO: Discusión no objetiva

Dejando la discusión de lado, si vamos a hablar de optimizaciones en serio vayamos directamente al código ensamblador, porque jugar con palabras de código humanizado no representa precisamente una optimización para la PC, sino más bien para REDUCIR líneas de texto que dan la impresión VISUAL de una simplificación.

Encontré una versión en ASM, hecha por sk0r

__declspec(naked) int __stdcall m_atoi(char* szTarget, unsigned int dwLength)
{
#define SUB_OFFS 48

__asm {
push ebp; //Save old framepointer value
mov ebp, esp; //Copy ESP into EBP -> EBP:[Old-EBP:4][Ret-Addr:4][dwLength:4][szTarget:4]
sub esp, 5; //Allocate 5 bytes [EBP-4]: unsigned int dwResult, [EBP-5]:char cMinusChar
mov dword ptr [ebp-4], 0; //Zero bytes of dwResult value. dwResult holds entire result value
mov byte ptr[ebp-5], 0; //Zero byte of cMinusChar. cMinusChar holds first char @szTarget for '-' check

cmp szTarget, 0; //Check if szTarget is a null pointer
je fEnd; //If so goto function end
cmp dwLength, 0; //Check if string length is zero
je fEnd; //If so goto function end

//Save registers for use
push ebx; //Holds mulitplied value of current positon.
push ecx; //Used for loop cmd
push edx; //For saving temporary stuff
push esi; //Holds start address + length of string
pushf; //For modifying direction flag

mov ebx, 1; //Set to one. The first position is the ones, second tens, third hundrets, etc.
mov ecx, dwLength; //Copy length to ECX for counting

mov esi, szTarget; //Copy string address to ESI
add esi, ecx; //Add string length
dec esi; //Decrement not to go too far (because of zero position)

push eax; //Save EAX temorarly
mov eax, szTarget; //Copy string address to EAX
mov al, byte ptr[eax]; //Copy the first byte to AL
mov byte ptr[ebp-5], al; //Copy it to EBP-5 (cMinusChar)
pop eax; //Restore EAX

cmp byte ptr[ebp-5], '-'; //Check if the char is a minus char
jne fOvr1; //If not goto fOvr1
dec ecx; //Decrement, because we ignore the '-' char to not corrupt the entire number

fOvr1:
std; //Set direction flag to 1 to go from hight to low addresses
fLoop:
xor eax, eax; //Clear bits of EAX
lodsb; //Copy byte at [ESI] to AL and extend ESI (in this case decrement)
sub al, SUB_OFFS; //Substract offset to make from char to real number
mul ebx; //Multiplicate EAX with EBX depending on its current position. Ones with 1, Tens with 10, Hundrets with 100, etc.
mov edx, dword ptr[ebp-4]; //Copy entire result value to EDX
add edx, eax; //Add EAX on it
mov dword ptr [ebp-4], edx; //Copy back to result value

mov eax, ebx; //Copy EBX to EAX
mov ebx, 10; //Copy 10 to EBX
mul ebx; //Multiply with 10 to go to the next positon: 1*10 = 10, 10*10 = 100, 100*10 = 1000, etc
mov ebx, eax; //Copy back to EBX

loop fLoop; //Goto fLoop and decrement ECX if not already zero

cmp byte ptr[ebp-5], '-'; //Check if first char was '-'
jne fOvr2; //If not goto fOvr2
mov eax, [ebp-4]; //Copy result value to EAX
mov ebx, -1; //Copy -1 to EBX
imul ebx; //Make signed multiplication to make a positive value to a negative one
mov [ebp-4], eax //Copy back to result value

fOvr2:
//Restore all used registers
popf;
pop esi;
pop edx;
pop ecx;
pop ebx;

fEnd:
mov eax, dword ptr[ebp-4]; //Copy result value to EAX for result
add esp, 5; //Remove both stack variables
pop ebp; //Restore EBP
ret 8; //Restore Ret-Address and remove the 8 argument bytes
}
}

Me cerraron el Windows Live Spaces, entonces me creé un WordPress XD
http://etkboyscout.wordpress.com/

avesudra

#8
Hola, que yo sepa atoi ya no se usa pues está obsoleta e itoa no está definida en el estándar de C como decía rir3760 en lugar de todo ello habría que usar:
long int strtol (const char* str, char** endptr, int base);

Referencia: http://www.cplusplus.com/reference/cstdlib/strtol/
Información de atoi obsoleta en la página de la libc: http://www.gnu.org/software/libc/manual/html_node/Parsing-of-Integers.html

Y para itoa se puede usar esto(que lo único que arregla es la portabilidad):
int sprintf ( char * str, const char * format, ... );

En teoría lo de las conversiones de bases debería funcionar con esas funciones.

PD: Digo esto porque tiene poco sentido ponerse a reinventar atoi e itoa ( si es para aprender y practicar si lo tiene ) cuando estas no son usadas o no deberían usarse.

¡Un saludo!
Regístrate en

85

Muy cierto, en realidad no debí haber creado el topic XD ya que siempre alguien lo va a hacer de una forma diferente, o arreglando uno existente, habría miles de implementaciones y en muchos lenguajes. Pero aveces está bueno para el aprendizaje
Me cerraron el Windows Live Spaces, entonces me creé un WordPress XD
http://etkboyscout.wordpress.com/