n-Damen-Problem lösen mit dynamischem mehrdim. Array

[n0Br4iN3r]

Ihr kennt doch sicher das n-Damen-Problem. Es geht dabei um ein Schachbrett mit n*n Feldern. Wie viele Damen (gleicher Farbe) kann man setzen, ohne dass sie sich gegenseitig schlagen?
Ich wollte den Algorithmus für einen AVR (ATmega in C schreiben, scheitere aber daran, dass ich das 2 dimensionale Array, in dem das "Schachbrett" gespeichert ist, zwar dynamisch allokieren kann (mit malloc bzw. calloc) und alles wunderbar läuft, aber der Speicher geht mir schon bei n=10 aus (malloc liefert NULL). Die Version mit einem statischen Array funktioniert problemlos (bei n=20 dauert das ganze ~3min).
Kennt ihr noch eine Methode, ein 2dim. Array dynamisch anzulegen bzw. wisst ihr, welchen Fehler ich haben könnte? (Ich weiß, malloc ist auf Embedded Systemen nicht allzu empfehlenswert, aber ich kenne keine andere Methode mit AVR-GCC dynamisch zu arbeiten)

mfg n0Br4iN3r

PS: Sorry dass ich den Beitrag schon in einem anderen Bereich gesendet hab, hab den Bereich übersehen - und hierhin passt er am besten.

[PicNick]

Ich verwende den Heap auf Controllern nicht, daher etwas dumme Fragen:
Kommt sicher auch auf die xAlloc-Anweisung an. Im Grund muß er ja zu jeder allocation einen Header dazulegen, der euch Platz braucht. Und wie die Heapverwaltung designed ist, weiß ich auch nicht.
Welchen Vorteil hast du, wenn du "dynamisch" arvbeitest ?

[SprinterSB]

malloc() und calloc() haben einen recht großen Overhead, was RAM und Flash-Verbrauch angeht. Immerhin muss eine Liste der allokierten Blöcke verwaltet werden, und das frisst RAM. Ausserdem führen aufeinander folgende malloc/free Zyklen zu einer Speicherfragmentierung, so daß evtl kein passender Block mehr verfügbar ist.
Seltsamerweise kennt avr-gcc kein alloca(), aber so geht's:

#include <stdlib.h>

void foo (unsigned short nbytes)
{
	unsigned short i;
	unsigned char *buf;
	
	buf = (unsigned char*) __builtin_alloca ((size_t) nbytes);
	
	for (i=0; i < nbytes; i++)
		buf[i] = 0;
}

Synopsis:
void* __builtin_alloca (size_t nbytes);

__builtin_alloca() ist keine libc-Funktion wie malloc() und calloc(), sondern ein Builtin von GCC.
Der Speicherplatz wird auf dem Stapel angelegt, indem einfach der Stackpointer entsprechend angepasst wird:

	.text
.global	foo
	.type	foo, @function
foo:
/* prologue: frame size=0 */
	push r28
	push r29
	in r28,__SP_L__
	in r29,__SP_H__
/* prologue end (size=4) */
	in r20,__SP_L__	 ;  tmp47	 ;  41	*movhi/7	[length = 2]
	in r21,__SP_H__	 ;  tmp47
	in r18,__SP_L__	 ; 	 ;  76	*movhi/7	[length = 2]
	in r19,__SP_H__	 ; 
	sub r18,r24	 ; , nbytes	 ;  11	subhi3/1	[length = 2]
	sbc r19,r25	 ; , nbytes
	in __tmp_reg__,__SREG__	 ;  77	*movhi/6	[length = 5]
	cli
	out __SP_H__,r19	 ; 
	out __SREG__,__tmp_reg__
	out __SP_L__,r18	 ; 
	subi r18,lo8(-(1))	 ;  buf,	 ;  12	*addhi3/4	[length = 2]
	sbci r19,hi8(-(1))	 ;  buf,
	sbiw r24,0	 ;  nbytes	 ;  52	tsthi/1	[length = 1]
	breq .L7	 ; ,	 ;  53	branch	[length = 1]
	movw r30,r18	 ;  buf, buf	 ;  68	*movhi/1	[length = 1]
.L5:
	st Z+,__zero_reg__	 ; ,	 ;  25	*movqi/3	[length = 1]
	sbiw r24,1	 ;  i,	 ;  70	*addhi3/3	[length = 1]
	brne .L5	 ; ,	 ;  72	branch	[length = 1]
.L7:
	in __tmp_reg__,__SREG__	 ;  44	*movhi/6	[length = 5]
	cli
	out __SP_H__,r21	 ;  tmp47
	out __SREG__,__tmp_reg__
	out __SP_L__,r20	 ;  tmp47
/* epilogue: frame size=0 */
	pop r29
	pop r28
	ret

Vom Overhead ist so was optimal, allerdings ist das Bereich nicht vorinitialisiert und muss auch nicht freigegeben werden, das geschieht am Ende des C-Blocks automatisch. Der Bereich ist daher nur innerhalb des Blocks gültig, der ihn beschafft hat. Mit return einen Zeiger auf den Bereich rausliefern ist also nicht.
...und ein Laufzeit-Check ob der Platz noch ausreicht scheints auch nicht zu geben, evtl kann man das selber erledigen.
Mit gcc-Option -fstack-check wird anderer Code generiert, vielleicht tut's die ja schon...?

::Edit::
...und ANSI-C ist alloca() auch nicht, sondern GNU-C.
avr-gcc -ansi ...
wird das also anmeckern, sollte zumindest.

[n0Br4iN3r]

Heap etc. habe ich beim Standard belassen - einfach nur einen calloc-Aufruf für 2-dimensionale Arrays. Am besten poste ich den Code.
Ich mach es dynamisch weil ich dann nicht jedes mal den AVR für eine neue Dimension n neu programmieren muss.

mfg n0Br4iN3r

[n0Br4iN3r]

Sehr gut... mit alloca gehts.
Danke SprinterSB, auf das wär ich nicht so schnell gekommen. Ich kenne zwar alloca, wusste aber nicht, dass man diese Funktion in AVR-GCC verwenden kann.

mfg n0Br4iN3r

[SprinterSB]

Das sollte mit __builtin_alloca() gehen, wenn du dein Programm etwas umstrukturierst.

N = USART_recvChar()-48;

Die 48 steht wohl für '0', Zahlen größer 9 sind da nicht leicht einzutippen, vielleicht macht das schon Probleme?

brett = calloc(N, sizeof(char *));
brett[i] = calloc(N, sizeof(char));

Ich find da irgendwie kein passenden free(...)

Mit __builtin_alloca() kannst du nicht in einer Schleife allokieren --> alles in einem Stück allokieren und selber verwalten. Du weisst ja, wie viel Platz du brauchst und wie er organisiert sein soll.

Du kannst viel Spatz sparen, wenn du für eine Zelle nicht ein Byte verbrätst, sondern nur ein Bit. Das reduziert den Speicherbedarf auf \sqrt{1/8}, also auf 36%.

Aufräumarbeiten kannst du dir nach einem Durchlauf auch sparen, indem du einen Soft-Reset machst

goto *((void**) 0);

[ba4_philipp]

Wie ich schon in dem anderen Thread meinte: Man kann das Problem auch geschlossen lösen. Ist dann aber natürlich nicht so schicken zu programmieren