Comparar y concatenar cadenas. Se reimplementan strcmp,
strncmp, strcat, strncat, strstr y
strlcat. 6 ejercicios (ex00–ex05); todos con funciones autorizadas: ninguna.
strcmp — El hilo conductor del módulo.
Comparar dos cadenas no es «¿son iguales?» sino «¿cuál va antes?». El contrato de la libc es preciso:
se recorren ambas byte a byte hasta el primer par que difiere, y se devuelve la
resta de esos dos bytes (interpretados como unsigned char). El signo del
resultado es lo único que importa: negativo si s1 va antes, positivo si va después, 0 si
son idénticas. De ahí sale el orden lexicográfico —el del diccionario, pero según
ASCII— sobre el que se construyen sort, los índices y media informática. Todo el módulo
gira en torno a leer dos punteros en paralelo y decidir con el primer byte que no coincide.C 03 es el primer módulo en el que se leen dos cadenas a la vez, y para defenderlo hacen falta unas cuantas ideas de cómo C guarda el texto y los números. Aquí está cada una explicada desde cero y con un ejemplo sacado del propio módulo. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.
\0)En C no existe un tipo «cadena»: una cadena es una fila de char seguidos en
memoria que acaba en un byte con valor 0, el terminador nulo, que se escribe
'\0'. La cadena no guarda su longitud en ningún sitio; la única forma de saber dónde
acaba es avanzar hasta encontrar ese 0. "Hola" ocupa 5 bytes: H o l a \0.
Por eso todos los bucles del módulo tienen la forma while (s[i]): un
char que vale 0 es «falso» y el bucle para. Y por eso ft_strcat tiene que
volver a escribir el \0 al final: el de dest lo ha pisado el primer
carácter de src, y sin terminador nadie sabría dónde acaba el resultado.
Cada byte de la memoria tiene un número, su dirección. Un puntero es una variable que
guarda una dirección. char *s1 no es la cadena: es la dirección de su primer carácter.
Cuando ft_strcmp(s1, s2) recibe dos cadenas, en realidad recibe dos direcciones y lee
lo que hay a partir de ellas.
Las funciones que modifican (ft_strcat, ft_strncat,
ft_strlcat) pueden cambiar el texto de quien las llama justamente porque reciben la
dirección del original, no una copia. Y ft_strstr no devuelve un trozo nuevo de
cadena, sino una dirección que apunta dentro de str.
Sumar un entero a un puntero lo avanza ese número de elementos: si str apunta a la
H de "Hola mundo", str + 5 apunta a la m. La
notación de corchetes es la misma cosa escrita de otra forma: str[i] significa
exactamente *(str + i), «lo que hay i posiciones más allá».
De ahí que en ft_strstr sea igual devolver str + i (como en la página)
que &str[i] (como en el repo): las dos expresiones dan la dirección del carácter
i. Y dest[i + j] en ft_strcat es «j posiciones después del final de
dest».
NULL: el puntero que no apunta a nadaNULL es un valor especial de puntero que significa «ninguna dirección». Vale 0, y
se puede escribir NULL (necesita <stddef.h> o
<stdlib.h>), 0 o (void *)0. Leer a través de él
(*NULL) hace que el programa muera con segmentation fault.
En C 03 lo usa ft_strstr para decir «no está»: la página devuelve 0 y
el repo (void *)0, que es lo mismo, sin incluir ninguna cabecera. Quien llama tiene que
comprobarlo antes de imprimir el resultado.
Un búfer es un trozo de memoria reservado para guardar datos, por ejemplo
char dest[100]. Su tamaño es fijo: si escribes más de lo que cabe, los bytes de más
caen encima de lo que haya al lado (otras variables, la dirección de vuelta de la función…). Eso es
un desbordamiento de búfer (buffer overflow), y ha sido durante décadas la puerta
de entrada de muchísimos ataques.
ft_strcat y ft_strncat no saben cuánto mide dest: si no
cabe, desbordan sin enterarse. ft_strlcat recibe ese tamaño en size y no
escribe nunca más allá.
Para el ordenador un carácter es un número. ASCII es la tabla que dice qué número va con cada
letra: '0' es 48, 'A' es 65, 'a' es 97, el espacio es 32.
Solo define los valores 0–127; lo que hay de 128 a 255 depende de la codificación (en UTF-8, una
é son dos bytes por encima de 127).
Como las mayúsculas van antes que las minúsculas, ft_strcmp("Zorro", "abeja") dice
que «Zorro» va antes: 90 es menor que 97. ft_strcmp("Saludos", "Salux") se decide en
la cuarta letra: 'd' (100) menos 'x' (120) da -20.
char con signo y unsigned charUn byte tiene 8 bits y puede guardar 256 valores. Si el tipo es unsigned char, se
leen como 0..255. Si es signed char, como −128..127: el mismo byte
0x80 vale 128 en un caso y −128 en el otro. El char a secas es uno u otro
según la plataforma (con signo en x86, sin signo en ARM Linux).
El man strcmp dice que se comparan como unsigned char. Con el cast,
ft_strcmp("test\200", "test\177") da positivo (128 − 127 = 1), igual que la de la
libc; sin el cast, en x86 el \200 valdría −128 y daría negativo. Es uno de los casos que
prueba el test del pack.
unsigned int y la vuelta por abajoUn unsigned int no tiene negativos: con 32 bits va de 0 a 4294967295. Las cuentas
se hacen «en círculo» (módulo 2³²): pasarse por arriba vuelve a 0 y bajar de 0 da el máximo. A
diferencia de los int con signo, esto está definido por el estándar, no es un error
del compilador, pero casi siempre es un error tuyo.
En ft_strncmp, con n = 0, la expresión n - 1 vale
4294967295 (medido con un printf("%u")). Sin el if (n == 0) del principio,
el bucle tendría permiso para seguir comparando casi sin límite.
Es lo que el estándar de C llama a las situaciones para las que no promete nada: leer fuera de un
array, leer a través de NULL, desbordar un int con signo… El programa
puede funcionar, dar basura, morir con un segfault o comportarse distinto con otro
compilador. «A mí me funciona» no demuestra nada.
En C 03 aparece cada vez que una función escribe o lee más allá de lo que tiene: un
ft_strcat sobre un dest sin sitio, o una cadena sin \0 que
los bucles recorrerían hasta encontrar un cero por casualidad.
Es el orden del diccionario generalizado: se comparan las dos palabras letra a letra y decide la primera letra distinta. Si una se acaba antes y hasta ahí eran iguales, la más corta va primero («ab» antes que «abc»). La única diferencia con un diccionario es que el valor de cada letra lo da la tabla ASCII, así que «Zorro» va antes que «abeja».
ft_strcmp implementa exactamente esto: el bucle busca la primera posición distinta, y
el «se acaba antes» sale solo porque el \0 vale 0 y es menor que cualquier letra.
ft_strcmp("ab", "abc") compara '\0' con 'c' y da negativo.
manEl contrato es lo que una función promete a quien la llama: qué recibe, qué devuelve y qué
garantiza. El de strcmp promete solo el signo del resultado (negativo, cero o
positivo), no un valor concreto. El de strncat promete poner siempre el
\0; el de strncpy, no. Todo eso está en el manual: man 3 strcmp
(la sección 3 es la de las funciones de biblioteca).
Cada ejercicio de C 03 dice «reproduce el comportamiento de la función X (man X)»: lo que la
Moulinette compara es el contrato, así que el man es el enunciado de verdad.
En A && B, C evalúa primero A, y si es falso ya no evalúa
B: el resultado va a ser falso de todas formas. Con || igual, pero parando
en el primer verdadero. El orden de las condiciones importa.
En while (s1[i] && s1[i] == s2[i]), si s1 ya se acabó no se
llega a comparar. Y en ft_strncmp la guarda i < n - 1 va la primera para
que, al llegar al límite, no se lea ni un carácter más de lo permitido.
Una subcadena es un trozo seguido de otra cadena: «mundo» es subcadena de «Hola mundo mundial», «Hmo» no (sus letras están, pero no juntas). Buscar dónde aparece una cadena dentro de otra es la búsqueda de patrones (pattern matching); al texto donde se busca se le suele llamar pajar y a lo buscado, aguja.
ft_strstr(str, to_find) es la versión más directa: probar cada posición de
str como posible comienzo. Con "aaab" y "aab", el intento en la
posición 0 casa dos letras y falla en la tercera; el de la posición 1 casa entero, y se devuelve
"aab".
La complejidad dice cómo crece el trabajo cuando crece la entrada. O(n) significa «proporcional a
n»: ft_strcmp y ft_strcat miran cada carácter una vez, así que una cadena
el doble de larga cuesta el doble.
ft_strstr tiene dos bucles anidados: para cada una de las n posiciones de
str, hasta m comparaciones con to_find. En el peor caso son unas n·m, de
ahí O(n·m). Algoritmos como KMP o Boyer–Moore bajan a O(n + m) recordando lo que ya casó, pero aquí
no hacen falta.
Truncar es cortar: si el resultado no cabe en el búfer, se guarda solo el principio. El problema de truncar en silencio es que quien llama no se entera de que le falta un trozo.
ft_strlcat lo resuelve devolviendo la longitud que habría tenido el resultado
completo. strlcat con "Hola", " mundo" y
size = 8 deja "Hola mu" (7 caracteres y el \0) y devuelve 10.
Como 10 ≥ 8, quien llama sabe que se ha truncado y que necesitaría un búfer de 11.
strlcat es «rara»strcmp, strcat o strstr son del C estándar y están en
cualquier sistema. strlcat y strlcpy las inventaron en OpenBSD (1998)
como alternativa segura, y durante años la biblioteca de C de Linux (glibc) se negó a incluirlas;
llegaron en la versión 2.38 (2023). En macOS, que viene de BSD, siempre han estado.
Por eso, para comparar con la de verdad en un Linux con glibc antigua hay que enlazar
libbsd (#include <bsd/string.h> y -lbsd), y por eso el
test del pack trae su propia ref_strlcat en lugar de llamar a la del sistema.
Es el corrector automático de 42. Compila cada ejercicio con cc -Wall -Wextra
-Werror junto a su propio main, lo ejecuta con sus casos y compara el resultado
con el esperado. Es muy estricta y no se discute con ella: un warning, una salida distinta, un
segfault o un cuelgue y el ejercicio cuenta como fallado. Según el enunciado, la evaluación
tiene dos fases: primero te corrigen compañeros de la piscine y después la Moulinette.
Como pone su propio main, si tu archivo también define uno el enlazado falla
(«duplicate symbol _main»). El enunciado permite dejar el main de pruebas,
pero comentado.
La Norma es el estilo de código obligatorio en 42: funciones de 25 líneas como mucho, 5 funciones
por archivo, declaraciones al principio separadas por una línea en blanco, tabulaciones, nada de
for, de do…while ni de switch… norminette es el
programa que la comprueba. Si falla la Norma, la nota es 0 aunque el código funcione.
El enunciado de C 03 pide pasarla con -R CheckForbiddenSourceHeader, y la Moulinette
hace lo mismo. Los seis archivos del repo dan OK! con esa opción.
Reproducir strcmp: comparar dos cadenas y devolver un entero negativo, cero o positivo.
int ft_strcmp(char *s1, char *s2)
{
int i;
i = 0;
while (s1[i] && s1[i] == s2[i])
i++;
return ((unsigned char)s1[i] - (unsigned char)s2[i]);
}
El bucle avanza mientras no se acabe s1 y los caracteres coincidan. Se para
en dos casos: se encontró una diferencia, o se llegó al final de s1. En ambos, la resta
s1[i] - s2[i] da la respuesta correcta: si son iguales hasta el \0 de las
dos, esa resta es 0. El casting a unsigned char es parte del contrato: garantiza que la
comparación trate los bytes como 0–255, igual que la strcmp real.
unsigned char?. En muchos sistemas
char es con signo, así que un byte > 127 valdría negativo. Sin el cast,
comparar un carácter «normal» con uno acentuado o binario daría un signo equivocado y el orden
saldría del revés. Es un detalle diminuto que separa una strcmp «que parece funcionar»
de una correcta: la Moulinette prueba exactamente estos bordes.Como strcmp pero comparando a lo sumo n caracteres.
int ft_strncmp(char *s1, char *s2, unsigned int n)
{
unsigned int i;
if (n == 0)
return (0);
i = 0;
while (i < n - 1 && s1[i] && s1[i] == s2[i])
i++;
return ((unsigned char)s1[i] - (unsigned char)s2[i]);
}
La guarda n == 0 al principio no es opcional: como n es
unsigned, escribir n - 1 con n = 0 no da −1, sino
4294967295 (envuelve por abajo), y el bucle recorrería memoria hasta petar. Con esa
comparación cubierta, el bucle avanza hasta n − 1 y compara ahí el último par.
unsigned no tienen números negativos: al bajar de 0 dan la vuelta al valor máximo. Es la
misma trampa que aparece en bucles while (i >= 0) con i sin signo (nunca
terminan). Aprender a desconfiar de las restas sobre unsigned es una de las lecciones
duraderas de este ejercicio.Pegar src al final de dest y devolver dest.
char *ft_strcat(char *dest, char *src)
{
int i;
int j;
i = 0;
while (dest[i])
i++;
j = 0;
while (src[j])
{
dest[i + j] = src[j];
j++;
}
dest[i + j] = '\0';
return (dest);
}
Dos fases: primero i se planta en el \0 de dest (su
longitud), y luego se copia src a partir de ahí, en dest[i + j]. Al acabar
hay que volver a poner el terminador, porque hemos sobrescrito el que tenía dest.
strcat asume que
dest tiene sitio de sobra para lo que le pegas. No hay comprobación de tamaño: si no
cabe, escribes fuera del búfer. Es el mismo pecado original que strcpy, y la razón de
que exista strlcat (ex05). Verlo aquí en su versión «ingenua» hace que la «segura» del
final del módulo tenga sentido.Concatenar como mucho nb caracteres de src.
char *ft_strncat(char *dest, char *src, unsigned int nb)
{
unsigned int i;
unsigned int j;
i = 0;
while (dest[i])
i++;
j = 0;
while (j < nb && src[j])
{
dest[i + j] = src[j];
j++;
}
dest[i + j] = '\0';
return (dest);
}
Idéntico a strcat salvo la guarda extra j < nb en el segundo bucle.
A diferencia de strncpy, aquí strncat sí añade siempre el
\0 final: es un detalle de la especificación que conviene recordar de memoria.
n. Las variantes con n
(strncpy, strncmp, strncat) acotan cuántos bytes tocan, pero
cada una decide de forma distinta qué hacer con el terminador. No hay una regla uniforme: hay que
leer el man de cada una. Descubrir esas asimetrías es parte del oficio.Buscar la primera aparición de to_find dentro de str y devolver un
puntero a ella (o NULL si no está). Si to_find es vacío, devolver
str.
char *ft_strstr(char *str, char *to_find)
{
int i;
int j;
if (!to_find[0])
return (str);
i = 0;
while (str[i])
{
j = 0;
while (str[i + j] && str[i + j] == to_find[j])
j++;
if (!to_find[j])
return (str + i);
i++;
}
return (0);
}
Es una búsqueda de doble bucle: por cada posición i de str, el bucle
interno intenta casar to_find carácter a carácter. Si el interno llega al
\0 de to_find (!to_find[j]), significa que casó entero, y se
devuelve el puntero al inicio de la coincidencia, str + i.
strstr es coincidencia de patrones (pattern matching) en
su forma más directa, O(n·m). Los algoritmos serios de búsqueda (KMP, Boyer–Moore) optimizan
justamente este doble bucle. Antes de mejorar algo, hay que saber escribir la versión honesta: eso
es este ejercicio.La concatenación «segura» de BSD. Añade src a dest sin pasarse de
size, termina siempre en \0, y devuelve la longitud que habría tenido el
resultado (útil para detectar truncamiento).
unsigned int ft_strlcat(char *dest, char *src, unsigned int size)
{
unsigned int dlen;
unsigned int slen;
unsigned int i;
dlen = 0;
while (dest[dlen] && dlen < size)
dlen++;
slen = 0;
while (src[slen])
slen++;
if (dlen == size)
return (size + slen);
i = 0;
while (src[i] && dlen + i + 1 < size)
{
dest[dlen + i] = src[i];
i++;
}
dest[dlen + i] = '\0';
return (dlen + slen);
}
Primero se mide dest pero sin pasar de size: si
dest no tiene \0 dentro del búfer, se considera «lleno» y se devuelve
size + slen sin copiar nada. Si hay sitio, se anexa dejando hueco para el terminador
(dlen + i + 1 < size). El valor devuelto es dlen + slen: la longitud
ideal, la haya cabido o no.
strlcat
sobre strncat es su valor de retorno: comparándolo con size, quien llama
sabe si se perdieron datos y puede reservar un búfer mayor y reintentar. Es un patrón de diseño de
API —«di siempre cuánto habrías necesitado»— que reaparece en muchas funciones de sistema
(snprintf, read…).Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado a fondo. Están agrupadas en: defender el código, casos límite, y Moulinette y Norma. Antes de mirar la respuesta, intenta contestar tú.
unsigned char en la resta de ft_strcmp?Porque el man dice que los bytes se comparan como unsigned char, y el
char de x86 tiene signo. Sin el cast, un byte por encima de 127 sería negativo:
"test\200" frente a "test\177" daría negativo, y la de la libc da positivo.
→ char con signo, ex00
ft_strcmp("Saludos", "Salux") da -20. ¿No debería dar -1?No hay un «debería»: el contrato solo garantiza el signo. Las dos respuestas son correctas. De
hecho, la strcmp de glibc dio -20 con esas cadenas leídas de argv y -1
cuando se le pasaron como literales (ahí gcc calcula el resultado al compilar). Por eso los tests
comparan signos y no valores. → contrato, ex00
ft_strcmp no comprueba también que no se acabe s2?Porque no hace falta: si s2 se acaba antes, s2[i] vale 0, y como
s1[i] no es 0 (lo comprueba la primera condición), s1[i] == s2[i] es falso
y el bucle para ahí. Añadir s2[i], como hace el repo, es redundante pero no está mal.
→ cortocircuito, ex00
ft_strncat pone siempre el \0? ¿Y strncpy?strncat sí, siempre: copia como mucho nb caracteres y después escribe
el terminador, así que dest necesita sitio para nb + 1. Con
"Hola", "abcdef" y 2 deja "Holaab". strncpy (C 02)
no: si src es igual de largo o más que n, no deja \0.
→ ex03
ft_strlcat y para qué sirve?La longitud que habría tenido la cadena completa: la de dest (contada como mucho hasta
size) más la de src. Si el valor devuelto es mayor o igual que
size, el resultado se ha truncado. Con "Hola", " mundo" y 8
deja "Hola mu" y devuelve 10. → truncamiento,
ex05
ft_strncmp(s1, s2, 0)?Devuelve 0 sin leer nada, por el if (n == 0). Sin esa guarda, n - 1
con n sin signo daría 4294967295 y el límite del bucle no serviría de nada.
→ unsigned, ex01
to_find es la cadena vacía? ¿Y si no está?Vacía: se devuelve str, lo dice el man y es lo primero que mira
ft_strstr; vale también para ft_strstr("", ""). Si no está: se devuelve
NULL, también con ft_strstr("", "a"). → NULL,
ex04
ft_strlcat si size es menor que la longitud de dest?No toca dest y devuelve size + strlen(src). Al medir dest
sin pasar de size, la cuenta para en size y se considera que no hay sitio.
Con size = 0 pasa lo mismo: devuelve la longitud de src. → ex05
dest no tiene sitio en ft_strcat?Se escribe fuera del búfer: comportamiento indefinido. ft_strcat no puede evitarlo
porque no sabe cuánto mide dest; asegurarlo es cosa de quien llama. Es justo lo que
arregla strlcat. → búfer, ex02
main en el archivo?Solo comentado. La Moulinette compila tu archivo con su propio main, y si hay dos el
enlazado falla. El test del pack avisa si el fuente todavía define main.
→ Moulinette
strlen o write?No: en los seis ejercicios las funciones autorizadas son «ninguna». Por eso cada función mide sus
longitudes con su propio bucle (dlen y slen en ft_strlcat).
Escribir tus propias funciones de ayuda en el mismo archivo sí está permitido, y cuentan para la
Norma. → ex05
Con norminette -R CheckForbiddenSourceHeader, como pide el enunciado. Recuerda que
no lo detecta todo: la Norma la comprueba también quien te evalúa, y si no se cumple la nota es 0.
→ norminette