L'épopée du fameux PP08
Posted: 19 May 2013, 23:18Bonjour à tous,
Suite à ma participation au concours Palprem qui allait étrangement trop vite par rapport à ce qu'il est possible de faire en Basic, beaucoup de personnes m'ont demandé d'expliquer comment j’avais fait pour calculer si rapidement le 5000è palindrome premier.
La réponse est pourtant simple, j'ai utilisé ndless.
Le classeur est en fait un programme ndless qui va lui-même ouvrir un "vrai" classeur Nspire.
En pratique voilà ce qu'il se passe:
Le code pour ceux que ça intéresse:
Je suis ouvert à toutes questions si besoin
.
...et si vous voulez télécharger le programme, c'est par ici: http://tiplanet.org/forum/archives_voir.php?id=14699
Suite à ma participation au concours Palprem qui allait étrangement trop vite par rapport à ce qu'il est possible de faire en Basic, beaucoup de personnes m'ont demandé d'expliquer comment j’avais fait pour calculer si rapidement le 5000è palindrome premier.
La réponse est pourtant simple, j'ai utilisé ndless.
Le classeur est en fait un programme ndless qui va lui-même ouvrir un "vrai" classeur Nspire.
En pratique voilà ce qu'il se passe:
- L'utilisateur ouvre le faux classeur, qui est en fait un programme ndless
- Le programme copie le vrai classeur dans un fichier bidon
- Le programme demande à l'OS d'ouvrir le classeur bidon en question
- Le programme va créer un hook dans la fonction qui évalue une expression mathématique (c'est à dire qu'il prend la main dans cette fonction, fait quelque chose, et laisse la fonction continuer à s’exécuter normalement).
- L'utilisateur voit un classeur Nspire ouvert
- Il tape palprem(42)
- L'OS arrive dans la fonction qui évalue l'expression mathématique, ce qui donne la main à mon programme
- Le programme regarde si l'expression rentrée est de la forme palprem(nombre) (si il ne trouve pas ça, il ne fait rien et redonne la main à l'OS qui va évaluer le calcul)
- Si il trouve le motif, il récupère le nombre et calcule le nombrième palindrome premier, et ce bien plus rapidement qu'en Basic
- Le programme place ensuite le nombrième palindrome à la place de "palprem(nombre)", et redonne la main à l'OS
- L'OS se retrouve alors avec un nombre à évaluer, et renvoie tout simplement ce nombre
- L'utilisateur voit ce nombre et va alors pouvoir l'utiliser pour.... (zut, ça sert à quoi les palindromes premiers?)
Le code pour ceux que ça intéresse:
Show/Hide spoilerAfficher/Masquer le spoiler
Quelques définitions dont l'adresse du hook
Le "vrai" classeur, qu'on inclut directement dans le binaire
Code pour trouver le n-ième palindrome premier. Adapté de : http://www.programmingsimplified.com/c/source-code/c-program-find-next-prime-palindrome
Ce bout permet d'enlever le hook quand on quitte le classeur
Vérifie si l'utilisateur a tapé palstring(nombre), et appelle si besoin palprime()
Ouvre le classeur et définit les hooks.
- Code: Select all
#include <os.h>
#include <libndls.h>
#include <stdint.h>
#include <inttypes.h>
static const unsigned int addr_exdoc_openclass[] = {0x10009B48, 0x10009B20, 0x10009AE8, 0x10009AE8};
#define EXDOC_OPENCLASS ((int(*)(char*, char*, int))nl_osvalue((int*)addr_exdoc_openclass, sizeof(addr_exdoc_openclass)/sizeof(addr_exdoc_openclass[0])))
static const unsigned int hook_addr_newclass[] = {0x10027558, 0x100274C4, 0x10026C54, 0x10026BEC};
#define HOOK_NEWCLASS nl_osvalue((int*)hook_addr_newclass, sizeof(hook_addr_newclass)/sizeof(hook_addr_newclass[0]))
static const unsigned int hook_addr_calc[] = {0x1006CBBC, 0x1006CAEC, 0x1006C2B8, 0x1006C210};
#define HOOK_ADDR_CALC nl_osvalue((int*)hook_addr_calc, sizeof(hook_addr_calc)/sizeof(hook_addr_calc[0]))
Le "vrai" classeur, qu'on inclut directement dans le binaire
- Code: Select all
extern void* __file_start__;
extern void* __file_end__;
asm(".globl __file_start__ \n"
".globl __file_end__ \n"
"__file_start__: \n"
".incbin \"palprem_class.tns\" \n"
"__file_end__: \n");
Code pour trouver le n-ième palindrome premier. Adapté de : http://www.programmingsimplified.com/c/source-code/c-program-find-next-prime-palindrome
- Code: Select all
uint32_t palprime(uint32_t m)
{
uint32_t n, t, r = 0, c, z = 0;
if(m<=5)
{
const int y[] = {0,2,3,5,7,11};
return y[m];
}
else
{
n = 101-2;
z = 5;
}
while(z<m)
{
printf("%" PRId32 " %" PRId32 "\n",z,n);
while (TRUE)
{
n+=2;
t = n;
/* Calculating reverse of number */
while(t)
{
r *= 10; /* Compound assignment operator r*=10 => r=r*10 */
r += t%10;
t /= 10;
}
/* if reverse equals original then it is palindrome */
if (r == n)
{
/* Checking prime */
if ((n%2 == 0) || (n%3 == 0) || (n%5 == 0))
goto suite;
c = 7;
while( c*c<=n)
{
if ((n%c == 0) || (n%(c+4) == 0))
break;
c+=6;
}
if (c*c>n)
break;
}
suite:
r = 0;
}
z++;
}
return n;
}
Ce bout permet d'enlever le hook quand on quitte le classeur
- Code: Select all
HOOK_DEFINE(newclass) {
HOOK_UNINSTALL(HOOK_ADDR_CALC, calc_change);
HOOK_UNINSTALL(HOOK_NEWCLASS , newclass);
HOOK_RESTORE_RETURN(newclass);
}
Vérifie si l'utilisateur a tapé palstring(nombre), et appelle si besoin palprime()
- Code: Select all
char resultstring[0x100];
const unsigned char palstring[] = {0x70, 0x00, 0x61, 0x00, 0x6C, 0x00, 0x70, 0x00, 0x72, 0x00, 0x65, 0x00, 0x6D, 0x00, 0x28, 0x00};
HOOK_DEFINE(calc_change) {
char* calcul = (char *) HOOK_SAVED_REGS(calc_change)[2];
if( !memcmp( calcul, &palstring, sizeof(palstring) ) )
{
uint32_t input = 0;
int offset = 0;
unsigned char currentn = calcul[sizeof(palstring)];
while( currentn>=0x30 && currentn<=0x39 )
{
input = input*10 + (currentn-0x30);
offset+=2;
currentn = calcul[sizeof(palstring)+offset];
}
if( offset!=0 && calcul[sizeof(palstring)+offset]==')' && calcul[sizeof(palstring)+offset+2]==0)
{
uint32_t result = palprime(input);
char resultstringbuf[0x80];
memset(resultstring , 0x0, 0x100);
memset(resultstringbuf, 0x0, 0x80);
sprintf(resultstringbuf, "%" PRId32 "", result);
int i;
for( i=0; i<0x80; i++ )
{
resultstring[2*i] = resultstringbuf[i];
}
HOOK_SAVED_REGS(calc_change)[2] = (int) resultstring;
} else
{
HOOK_SAVED_REGS(calc_change)[2] = (int) palstring;
}
} else
{
int i;
for( i=0; i<0x100; i++ )
{
if( calcul[2*i]=='p' && !memcmp( calcul+2*i, &palstring, sizeof(palstring)-2 ))
{
HOOK_SAVED_REGS(calc_change)[2] = (int) palstring;
break;
}
}
}
HOOK_RESTORE_RETURN(calc_change);
}
Ouvre le classeur et définit les hooks.
- Code: Select all
int main()
{
nl_set_resident();
FILE *tns_file;
tns_file = fopen("/logs/palprem.tns","wb");
fwrite (&__file_start__ , sizeof(char) , 4*(&__file_end__-&__file_start__), tns_file );
fclose(tns_file);
EXDOC_OPENCLASS("/logs","palprem.tns",1);
HOOK_INSTALL(HOOK_ADDR_CALC, calc_change);
HOOK_INSTALL(HOOK_NEWCLASS, newclass);
return 0;
}
Je suis ouvert à toutes questions si besoin
....et si vous voulez télécharger le programme, c'est par ici: http://tiplanet.org/forum/archives_voir.php?id=14699
