Autor Tema: Copiar matriz tridimensional en C  (Leído 7076 veces)

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

Desconectado planeta9999

  • Moderadores
  • DsPIC30
  • *****
  • Mensajes: 3520
    • Pinballsp
Copiar matriz tridimensional en C
« en: 04 de Diciembre de 2017, 08:47:06 »
¿ Sabeis cual es la manera más rapida de copiar una matriz tridimensional completa sobre otra ?.
He leído sobre strcpy y memcpy.

No tengo claro si strcpy realmente permite copiar una matriz sobre otra, leo que copia una cadena a una matriz, pero es que una cadena o string es realmente una matriz, aunque en mi caso como es tridimensional, seguramente ya no sirve.

memcpy leo que es lo más rápido, pero no estoy seguro si permite copiar una matriz tridimensional completa sobre otra idéntica. Mi duda radica en que no se como está organizada internamente en memoria una matriz tridimensional, para poder usar un puntero de origen a destino con posiciones contiguas de memoria. He visto algún ejemplo en el que solo copian una de las dimensiones completas de una matriz bidimensional o tridimensional, pero no la matriz al completo, o que todos los elementos deben de estar ubicados en posiciones de memoria contiguas tanto en origen como en destino.

Lo que no quiero es copiar la matriz barriéndola con bucles "for", eso me parece una chapuza, tiene que haber algo para hacer una copia directa.

Mi problema, es que tengo una matriz que se llena a partir de datos que entran por SPI/DMA. Por eso cuando esa matriz está llena, como la tengo que enviar por UDP (previo proceso y troceado de esos datos), necesito copiarla rápido a otra matriz de trabajo, porque si trabajo sobre la matriz original, mientras la estoy leyendo, ya se está actualizando por otro lado y me altera los datos.

Mi idea es copiar la matriz original y trabajar sobre la copia, mientras el resto de proceso puede seguir actualizando la matriz original.
« Última modificación: 04 de Diciembre de 2017, 08:50:04 por planeta9999 »

Desconectado juaperser1

  • Colaborador
  • DsPIC30
  • *****
  • Mensajes: 2980
Re:Copiar matriz tridimensional en C
« Respuesta #1 en: 04 de Diciembre de 2017, 09:10:20 »
¿Como es de grande? si no es demasiado grande puedes hacer un bucle anidado, no es ninguna chapuza, supongo que la velocidad del micro será bastante alta por lo tanto no deberías tener problemas, también puedes usar punteros a la matriz e ir copiando el dato que te interese en otra variable sin modificar la matriz, los punteros son una herramienta muy poderosa pero poca gente los utiliza por pereza de aprenderlos o por la dificultad, pero una vez se comprenden puedes hacer cosas de manera muy sencilla.


Desconectado planeta9999

  • Moderadores
  • DsPIC30
  • *****
  • Mensajes: 3520
    • Pinballsp
Re:Copiar matriz tridimensional en C
« Respuesta #2 en: 04 de Diciembre de 2017, 10:06:27 »
 

No, bucles no puedo hacer. Se trata de un proceso muy rápido de gestión de imágenes, eso me ralentizaría mucho, y seguramente mezclaría datos de la imagen actual sobre la nueva que ya está entrando por DMA.

La matriz se tiene que copiar completa, para tener una copia de trabajo, no me valen elementos sueltos, se va a procesar toda la matriz que contiene una imagen. El problema que tengo ahora es que al trabajar sobre la matriz original, se me mezcla una imagen con parte de la siguiente y me salen algunas pantallas malas.

Se que la solución pasa por hacer una copia de la matriz original, y trabajar sobre esa copia, pero esa copia tambien se tiene que hacer muy rápido, o me puede pasar lo mismo, que los nuevos datos que siguen entrando por DMA de manera continua, me ensucien también la copia de la matriz, y estaríamos igual.

Estoy casi seguro que con memcpy se puede hacer, lo iré probando. Lo que si parece es que todos los elementos de la matriz origen deben de ser contiguos en memoria, y lo mismo en la de destino.
« Última modificación: 04 de Diciembre de 2017, 10:12:16 por planeta9999 »

Desconectado tsk

  • PIC18
  • ****
  • Mensajes: 258
Re:Copiar matriz tridimensional en C
« Respuesta #3 en: 04 de Diciembre de 2017, 13:17:02 »
No necesariamente la matriz tiene que ser tridimensional para representar la imagen.

Recuerda que el DMA tiene la opción de levantar una interrupción cuando el buffer está a la mitad, por lo que podrías usar esa característica para simular dos buffer en un mismo arreglo o, en su defecto podrías crear una estructura, como te lo había comentado en otro hilo, donde tengas dos buffers. En cualquier caso, a la hora de que el DMA del SPI levante una interrupción, se le indica donde tiene que almacenar los siguientes datos (en el caso de dos buffers) y en ambos caso la rutina que envía los datos por UDP trabaja de forma independiente del DMA del SPI, ya que en la rutina de interrupción se indicaría cual buffer o sección contiene datos válidos.

Así te evitas la copia de datos a otra región de memoria.

Desconectado planeta9999

  • Moderadores
  • DsPIC30
  • *****
  • Mensajes: 3520
    • Pinballsp
Re:Copiar matriz tridimensional en C
« Respuesta #4 en: 04 de Diciembre de 2017, 13:54:23 »


Eso de configurar el DMA para que de manera alternada y automática vuelque en dos buffers, no se como hacerlo. Puedo simularlo por software, usando un campo a modo de switch, para que con un IF vuelque los datos del buffer a una u otra matriz, para ir alternando la matriz de trabajo.

De todas formas el buffer del DMA no es con el que trabajo directamente, ese buffer se copia con un memcpy a la matriz multidimensional, usando tres índices, y es cuando la matriz está totalmente llena, cuando se pasa a una función para procesarla.

Y la cosa aún se complica más, porque la matriz se llena como si fuera un registro de desplazamiento, así tampoco se podrían alternar. No puedo meter 3 planos de datos a una matriz, y luego pasarme a la otra, los datos que van entrando por el DMA van empujando a los planos de la matriz, de manera que siempre estén los 3 últimos que han entrado. Si las alternara, habría un vacío de 3 planos que dejarían de desplazar los datos en cada matriz.

Yo creo que con un memcpy se puede hacer un memcpy(&array2,&array1,sizeof(array2));, que duplique el array, creo que es algo bastante rápido.
« Última modificación: 04 de Diciembre de 2017, 14:04:42 por planeta9999 »

Desconectado Carl47D

  • PIC16
  • ***
  • Mensajes: 160
Re:Copiar matriz tridimensional en C
« Respuesta #5 en: 04 de Diciembre de 2017, 17:56:52 »
La implementación de memcpy copia los datos de la fuente al destino con un while, un for disfrazado.

Código: C
  1. #include <stddef.h> /* size_t */
  2. void *memcpy(void *dest, const void *src, size_t n)
  3. {
  4.     char *dp = dest;
  5.     const char *sp = src;
  6.     while (n--)
  7.         *dp++ = *sp++;
  8.     return dest;
  9. }

Se puede revisar como se almacena la matriz tridimencional en la memoria del micro, en caso de que se almacene de manera continua podrías usar DMA para copiar de memoria(matriz original) a memoria(matriz copia).

Desconectado colotron

  • PIC12
  • **
  • Mensajes: 73
    • Canal de YouTube
Re:Copiar matriz tridimensional en C
« Respuesta #6 en: 04 de Diciembre de 2017, 21:47:14 »
memcpy leo que es lo más rápido, pero no estoy seguro si permite copiar una matriz tridimensional completa sobre otra idéntica. Mi duda radica en que no se como está organizada internamente en memoria una matriz tridimensional, para poder usar un puntero de origen a destino con posiciones contiguas de memoria. He visto algún ejemplo en el que solo copian una de las dimensiones completas de una matriz bidimensional o tridimensional, pero no la matriz al completo, o que todos los elementos deben de estar ubicados en posiciones de memoria contiguas tanto en origen como en destino.

No deberías preocuparte por la estructura interna de los datos a copiar, podrías copiar un struct que tenga cualquier clase de campos y estaría bien. Mientras se pase puntero de origen, destino, y tamaño basta. Pero eso ya lo pusiste más abajo.

Mi problema, es que tengo una matriz que se llena a partir de datos que entran por SPI/DMA. Por eso cuando esa matriz está llena, como la tengo que enviar por UDP (previo proceso y troceado de esos datos), necesito copiarla rápido a otra matriz de trabajo, porque si trabajo sobre la matriz original, mientras la estoy leyendo, ya se está actualizando por otro lado y me altera los datos.

Mi idea es copiar la matriz original y trabajar sobre la copia, mientras el resto de proceso puede seguir actualizando la matriz original.

Mmmmm, si se quiere enviar una estructura de datos por puerto serie entonces ahí sí interesa el orden de los datos, porque hay que reconstruirlo del otro lado... pero si usas UDP supongo que no interesa perder paquetes de datos?

Eso de configurar el DMA para que de manera alternada y automática vuelque en dos buffers, no se como hacerlo. Puedo simularlo por software, usando un campo a modo de switch, para que con un IF vuelque los datos del buffer a una u otra matriz, para ir alternando la matriz de trabajo.

De todas formas el buffer del DMA no es con el que trabajo directamente, ese buffer se copia con un memcpy a la matriz multidimensional, usando tres índices, y es cuando la matriz está totalmente llena, cuando se pasa a una función para procesarla.

Y la cosa aún se complica más, porque la matriz se llena como si fuera un registro de desplazamiento, así tampoco se podrían alternar. No puedo meter 3 planos de datos a una matriz, y luego pasarme a la otra, los datos que van entrando por el DMA van empujando a los planos de la matriz, de manera que siempre estén los 3 últimos que han entrado. Si las alternara, habría un vacío de 3 planos que dejarían de desplazar los datos en cada matriz.

¿Pensaste en usar un esquema de doble buffer?
Si hay suficiente memoria RAM podrías hacer

uint8_t buffer1[TAMANO];
uint8_t buffer2[TAMANO];

uint8_t *bufferEntrada = buffer1;
uint8_t *bufferSalida = buffer2;

Entonces la principio se llena bufferEntrada = buffer1; cuando está lleno se intercambian:

swap(bufferEntrada, bufferSalida);
SPI_Recibir(bufferEntrada, TAMANO);
UDP_Enviar(bufferSalida, TAMANO);

Luego cuando se llena nuevamente el buffer de entrada se realiza la misma operación, la limitación es que la salida de datos (por UDP) tiene que ser más rápida que la entrada de datos (por SPI).

Esto tiene la ventaja de que no hay que perder tiempo copiando bloques de memoria, y la desventaja de que ocupa el doble de RAM.

Yo creo que con un memcpy se puede hacer un memcpy(&array2,&array1,sizeof(array2));, que duplique el array, creo que es algo bastante rápido.

Si los arrays estan definidos con corchetes:
uint8_t array1[indiceMax1][IndiceMax2][IndiceMax3];

Entonces no va el operador & porque ya array1 y array2 serían punteros:

memcpy(array2,array1,sizeof(array2));

Desconectado Carl47D

  • PIC16
  • ***
  • Mensajes: 160
Re:Copiar matriz tridimensional en C
« Respuesta #7 en: 04 de Diciembre de 2017, 22:34:53 »
No necesariamente la matriz tiene que ser tridimensional para representar la imagen.

Recuerda que el DMA tiene la opción de levantar una interrupción cuando el buffer está a la mitad, por lo que podrías usar esa característica para simular dos buffer en un mismo arreglo o, en su defecto podrías crear una estructura, como te lo había comentado en otro hilo, donde tengas dos buffers. En cualquier caso, a la hora de que el DMA del SPI levante una interrupción, se le indica donde tiene que almacenar los siguientes datos (en el caso de dos buffers) y en ambos caso la rutina que envía los datos por UDP trabaja de forma independiente del DMA del SPI, ya que en la rutina de interrupción se indicaría cual buffer o sección contiene datos válidos.

Así te evitas la copia de datos a otra región de memoria.

También evitaría el copiar datos de un lado a otro, el DMA es como un coprocesador que trabaja en paralelo al CPU del microcontrolador y los datos se podrían corromper mientras el procesador copia los datos de la fuente al destino (o eso se me imagina).
« Última modificación: 05 de Diciembre de 2017, 01:08:28 por Carl47D »

Desconectado KILLERJC

  • Colaborador
  • DsPIC33
  • *****
  • Mensajes: 8242
Re:Copiar matriz tridimensional en C
« Respuesta #8 en: 04 de Diciembre de 2017, 23:07:36 »
Citar
Lo que no quiero es copiar la matriz barriéndola con bucles "for", eso me parece una chapuza, tiene que haber algo para hacer una copia directa.

Te equivocaste de lenguaje parece, Y por mas que el lenguaje lo haga mucho mas facil como seria un overload del operador asignacion en C++ lo seguirias haciendo con un for.

Estas intentando correr contra el tiempo y no hay otra forma de realizar el copiado mas que con DMA si es que no queres usar un for/while como lo hace el memcpy por dentro y punteros.

Por otra parte el tema de usar 2 buffers es la solucion que estas buscando. Ya que tu problema hasta ahora es que estas corriendo como loco porque los datos te llegan de nuevo y no tenes donde ponerlos y tampoco lugar para donde procesarlos.
« Última modificación: 04 de Diciembre de 2017, 23:10:12 por KILLERJC »

Desconectado tsk

  • PIC18
  • ****
  • Mensajes: 258
Re:Copiar matriz tridimensional en C
« Respuesta #9 en: 05 de Diciembre de 2017, 02:17:36 »
No es que vayas a tener dos buffers por separado, es uno sólo, para eso se habilita la interrupción de mitad de buffer. Es como si particionaras, virtualmente, el buffer en dos unidades. Todo sacando provecho de las característica que nos provee el DMA.

También se habilita el modo circular, de tal forma que al terminar de llenar el buffer completo, el índice se regresa a cero, por lo que tendrías una recepción sin interrupciones.

Velo como un buffer del doble de tamaño que requieres para llenar tu buffer actual, ya que dentro de la interrupción se le indicaría cual sección está disponible (primera o segunda mitad del buffer) para enviar los datos por UDP y/o para ser procesado.

Si estás usando tres índices para llenar la matriz multi-dimensional, lo más seguro es que exista espacio para simplificar las cosas y a la vez reducir la complejidad de tu algoritmo, así como reducir el tiempo que se tarda en procesar los datos.

Imagina la complejidad de lo que tienes en este momento (O(N^3)). Si hacemos un simple ejercicio en C, sobre el tiempo requerido en iterar en un arreglo bidimensional (i,j) con una complejidad O(N^2) a un arreglo unidimensional (O(N)), obtenemos el siguiente resultado en 100000 iteraciones en un arreglo de tamaño 1000x3

Código: [Seleccionar]

ROW/COLUM iteration in two dimentional Array: Total Time: 1729.835000 ms
One dimentional Array: Total Time: 432.439000 ms
Ratio: 4.000183

Ahora imagina lo que se tarda un algoritmo de complejidad O(N^3) como el que estas implementando, para llenar el arreglo de 3 dimensiones. Desde ahí, creo que complicaste algo el sistema entero.

Si lo vez de forma gráfica. Para esta gráfica estoy suponiendo de forma burda, para simplificar, un micro a 180Mhz y que lo que está dentro de los ciclos for se ejecutan en un ciclo de reloj



El tiempo en O(N^3) se va por las nubes.

memcpy, se pude considerar O(N) pero si aprovechas el DMA es un tiempo que puedes usar para otras cosas o para asegurar que todo esté bien sincronizado y no haya perdida de datos.

Desconectado planeta9999

  • Moderadores
  • DsPIC30
  • *****
  • Mensajes: 3520
    • Pinballsp
Re:Copiar matriz tridimensional en C
« Respuesta #10 en: 05 de Diciembre de 2017, 06:32:34 »
Citar
Lo que no quiero es copiar la matriz barriéndola con bucles "for", eso me parece una chapuza, tiene que haber algo para hacer una copia directa.

Te equivocaste de lenguaje parece, Y por mas que el lenguaje lo haga mucho mas facil como seria un overload del operador asignacion en C++ lo seguirias haciendo con un for.

Estas intentando correr contra el tiempo y no hay otra forma de realizar el copiado mas que con DMA si es que no queres usar un for/while como lo hace el memcpy por dentro y punteros.

Por otra parte el tema de usar 2 buffers es la solucion que estas buscando. Ya que tu problema hasta ahora es que estas corriendo como loco porque los datos te llegan de nuevo y no tenes donde ponerlos y tampoco lugar para donde procesarlos.


No me he equivocado del lenguaje, porque parto de un programa que ya lo estaba haciendo, con la llamada a un función propia swapBuffers, que probablemente copia la matriz original en otra. Esa parte de programa no me sirve porque gestiona paneles led, que yo no necesito, pero el principio de funcionamiento es el mismo, trabajar sobre una copia de la matriz original.

Tampoco he dicho que no quiera usar UN for/while, he dicho que no quiero BARRER la matriz con BUCLES (en plural, tres bucles anidados), porque eso podría ser muy lento.

Que memcpy use un bucle no quiere decir que esté barriendo la matriz elemento a elemento con bucles anidados. Si es como se ha puesto aquí está barriendo la matriz con UN solo puntero, de lo que deduzco que todos los elementos de la matriz, aunque esta sea multidimensional, están en direcciones contiguas. Lo más probable es que use memcpy para duplicar la matriz en otra de trabajo.

Desconozco como funciona el tema de los dos buffers, pero como he comentado la matriz de trabajo tiene que ser solo una, porque los datos entran a modo de registro de desplazamiento.


Desconectado planeta9999

  • Moderadores
  • DsPIC30
  • *****
  • Mensajes: 3520
    • Pinballsp
Re:Copiar matriz tridimensional en C
« Respuesta #11 en: 05 de Diciembre de 2017, 06:33:31 »
 

Buscando en la librería del programa original, encontré la función que usan swapBuffers, y parece que en efecto usan el memcpy para hacer una copia de trabajo de la matriz original.

Lo que me da la sensación, es que no hay dos matrices, original y copia, sino una sola matriz con el doble de elementos, porque como se ve en este fuente, los punteros al original y la copia se están haciendo sobre la misma matriz. Supongo que al final es lo mismo, al trabajar con punteros, pero de esta manera es seguro que todos los elementos de la matriz están en direcciones contiguas de memoria, para que el memcpy pueda hacerse.


// waits until previous swap is complete
// waits until current swap is complete if copy is enabled
template <typename RGB, unsigned int optionFlags>
void SMLayerBackground<RGB, optionFlags>::swapBuffers(bool copy) {
    while (swapPending);

    swapPending = true;

    if (copy) {
        while (swapPending);
        copyRefreshToDrawing();
    }
}


template <typename RGB, unsigned int optionFlags>
void SMLayerBackground<RGB, optionFlags>::copyRefreshToDrawing() {
    memcpy(currentDrawBufferPtr, currentRefreshBufferPtr, sizeof(RGB) * (this->matrixWidth * this->matrixHeight));
}


template <typename RGB, unsigned int optionFlags>
SMLayerBackground<RGB, optionFlags>::SMLayerBackground(RGB * buffer, uint16_t width, uint16_t height) {
    backgroundBuffer = buffer;
    this->matrixWidth = width;
    this->matrixHeight = height;

    currentDrawBufferPtr = &backgroundBuffer[0 * (this->matrixWidth * this->matrixHeight)];
    currentRefreshBufferPtr = &backgroundBuffer[1 * (this->matrixWidth * this->matrixHeight)];

}



« Última modificación: 05 de Diciembre de 2017, 16:50:00 por planeta9999 »

Desconectado KILLERJC

  • Colaborador
  • DsPIC33
  • *****
  • Mensajes: 8242
Re:Copiar matriz tridimensional en C
« Respuesta #12 en: 05 de Diciembre de 2017, 08:38:23 »
Si, pero un memcpy no es lo que estas buscando vos, ya que tu problema es la velocidad de ejecucion respecto al llenado del buffer. Lo que te digo es que busques como realizar con DMA un doble buffer, asi mientras seguis llenando tenes tiempo de realizar esa copia.

Desconectado planeta9999

  • Moderadores
  • DsPIC30
  • *****
  • Mensajes: 3520
    • Pinballsp
Re:Copiar matriz tridimensional en C
« Respuesta #13 en: 05 de Diciembre de 2017, 20:02:56 »
Si, pero un memcpy no es lo que estas buscando vos, ya que tu problema es la velocidad de ejecucion respecto al llenado del buffer. Lo que te digo es que busques como realizar con DMA un doble buffer, asi mientras seguis llenando tenes tiempo de realizar esa copia.


Ya, pero es que así funciona en el programa original, en mi caso es lo mismo, solo que mi matriz copia es para otro uso distinto, pero el principio es el mismo, no es problema de velocidad.


He metido mi memcpy, y algo he hecho mal, porque el cliente me dice que le sale todo en blanco, vamos que el memcpy no me ha copiado nada. Esta matriz de 3 dimensiones, está definida de una manera bastante enrevesada, creo que ahí está el problema a la hora de encarar el memcpy correctamente.

No pillo muy bien la manera de definir esta matriz tridimensional. Primero define una matriz planes de una dimension, luego define una matriz wpc_plane bidimensional.  Lo que hace luego ya me pierdo wpc_plane* wpc_planes = (wpc_plane*) planes;, crea un puntero wpc_planes a wpc_plane multiplicado por planes, o eso creo.

¿ Es posible que no me copie nada porque en el memcpy, le estoy poniendo como cantidad de elementos a copiar sizeof(wpc_planes2), siendo wpc_planes2 un puntero ?.


//** Esta es la matriz original
uint16_t planes[PLANE_SIZE * PLANE_COUNT];
typedef uint16_t wpc_plane[ROW_COUNT][ROW_LENGTH];
wpc_plane* wpc_planes = (wpc_plane*) planes;


// Aqui he definido otra para copiar la original con memcpy
uint16_t planes2[PLANE_SIZE * PLANE_COUNT];
typedef uint16_t wpc_plane2[ROW_COUNT][ROW_LENGTH];
wpc_plane2* wpc_planes2 = (wpc_plane2*) planes2;


// Aqui el memcpy para copiar una matriz sobre otra
memcpy(wpc_planes2, wpc_planes, sizeof(wpc_planes2));


« Última modificación: 05 de Diciembre de 2017, 20:34:02 por planeta9999 »

Desconectado tsk

  • PIC18
  • ****
  • Mensajes: 258
Re:Copiar matriz tridimensional en C
« Respuesta #14 en: 05 de Diciembre de 2017, 21:01:59 »


//** Esta es la matriz original
uint16_t planes[PLANE_SIZE * PLANE_COUNT];
typedef uint16_t wpc_plane[ROW_COUNT][ROW_LENGTH];
wpc_plane* wpc_planes = (wpc_plane*) planes;


// Aqui he definido otra para copiar la original con memcpy
uint16_t planes2[PLANE_SIZE * PLANE_COUNT];
typedef uint16_t wpc_plane2[ROW_COUNT][ROW_LENGTH];
wpc_plane2* wpc_planes2 = (wpc_plane2*) planes2;


// Aqui el memcpy para copiar una matriz sobre otra
memcpy(wpc_planes2, wpc_planes, sizeof(wpc_planes2));

sizeof(wpc_planes2) te da el tamaño del puntero que va a ser dependiente de la arquitectura, como es de 32 bits, sólo te va a copiar los primeros 4 bytes. Tienes que hacerlo de la siguiente forma sizeof(*wpc_planes2)

Código: [Seleccionar]
ROW_COUNT = 100 ; ROW_LENGTH 3
sizeof(wpc_planes2) = 4
sizeof(*wpc_planes2) = 600

Me imagino que

PLANE_SIZE * PLANE_COUNT  = ROW_COUNT * ROW_LENGTH

Ve esta guía de las sugerencias de lo que se debe y no se debe de hacer en los sistemas embebidos

https://www.ipa.go.jp/files/000040508.pdf

Es parecido al MISRA C y de hecho se basan en ese, sólo que este lo descargas de forma gratuita y el MISRA C tiene un costo.


 

anything