C Piscine — C 03

Comparar y concatenar cadenas. Se reimplementan strcmp, strncmp, strcat, strncat, strstr y strlcat. 6 ejercicios (ex00–ex05); todos con funciones autorizadas: ninguna.

El contrato de 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.

GGlosario de teoría

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.

Cadenas y memoria

Cadena de C y terminador nulo (\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.

Puntero y dirección

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.

Índice y aritmética de punteros

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 nada

NULL 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.

Búfer y desbordamiento de búfer

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á.

Bytes y números

ASCII

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 char

Un 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 abajo

Un 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.

Comportamiento indefinido

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.

Comparar y buscar

Orden lexicográfico

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.

Contrato de una función y el man

El 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.

Evaluación en cortocircuito

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.

Subcadena y búsqueda de patrones

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".

Complejidad: O(n) y O(n·m)

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.

Truncamiento y longitud ideal

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.

BSD, glibc y por qué 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.

La entrega

Moulinette

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.

Norma y norminette

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.

ex00ft_strcmp

Prototipo: int ft_strcmp(char *s1, char *s2)

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.

Concepto — ¿por qué 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.

ex01ft_strncmp

Prototipo: int ft_strncmp(char *s1, char *s2, unsigned int n)

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.

Concepto — el underflow de los sin signo. Los 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.

ex02ft_strcat

Prototipo: char *ft_strcat(char *dest, char *src)

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.

Concepto — quien concatena, confía. 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.

ex03ft_strncat

Prototipo: char *ft_strncat(char *dest, char *src, unsigned int nb)

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.

Concepto — familias 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.

ex04ft_strstr

Prototipo: char *ft_strstr(char *str, char *to_find)

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.

Concepto — el primer algoritmo «de verdad». Hasta aquí todo eran recorridos lineales; 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.

ex05ft_strlcat

Prototipo: unsigned int ft_strlcat(char *dest, char *src, unsigned int size)

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.

Concepto — informar del truncamiento. La gracia de 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…).

?Preguntas probables de la evaluación

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ú.

Defender el código

¿Por qué el cast a 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

Tu 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

¿Por qué el bucle de 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

¿Qué devuelve 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

Casos límite

¿Qué pasa con 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

¿Y si 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

¿Qué hace 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

¿Qué pasa si 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

Moulinette y Norma

¿Puedo dejar un 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

¿Podías usar 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

¿Cómo has pasado la norminette?

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