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

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 (ATmega8) 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.

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 ?

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:

Code:

#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:

Code:

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

Liste der Anhänge anzeigen (Anzahl: 1)

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

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

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

Zitat:

Zitat von n0Br4iN3r

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?

Zitat:

Zitat von n0Br4iN3r

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 :-)

Zitat:

Zitat von software reset

goto *((void**) 0);

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 ;)