2013-12-13 5 views
9

Ho incontrato un bug piuttosto strano. Il seguente piccolo pezzo di codice utilizza una matematica piuttosto semplice.ProGuard può causare calcoli errati

protected double C_n_k(int n, int k) 
{ 
    if(k<0 || k>n) 
    return 0; 
    double s=1; 
    for(int i=1;i<=k;i++) 
    s=s*(n+1-i)/i; 
    return s; 
} 

Modifica Utilizzando ProGuard può farlo andare male su alcuni dispositivi. Lo ho confermato su HTC One S Android 4.1.1 build 3.16.401.8, ma a giudicare dalle e-mail che ho ricevuto, sono interessati molti telefoni con Android 4+. Per alcuni di loro (Galaxy S3), i telefoni con marchio operatore americano sono interessati, mentre le versioni internazionali non lo sono. Molti telefoni non sono interessati.

Di seguito è riportato il codice di attività che calcola C (n, k) per 1 < = n < 25 e 0 < = k < = n. Sul dispositivo sopra menzionato la prima sessione fornisce risultati corretti, ma i lanci successivi mostrano risultati errati, ogni volta in posizioni diverse.

ho 3 domande:

  1. Come può essere? Anche se ProGuard ha fatto qualcosa di sbagliato, i calcoli dovrebbero essere coerenti tra dispositivi e sessioni.

  2. Come possiamo evitarlo? So che sostituire double con long va bene in questo caso, ma non è un metodo universale. L'eliminazione utilizzando double o il rilascio di versioni non offuscate è fuori questione.

  3. Quali versioni di Android sono interessate? Ero abbastanza veloce con fissandola nel gioco, quindi ho solo sapere che molti giocatori hanno visto, e almeno la maggior parte aveva Android 4,0

Overflow è fuori discussione, perché a volte vedo errore nel calcolo C(3,3)=3/1*2/2*1/3. Di solito i numeri errati iniziano da qualche parte in C (10, ...), e sembrano come se un telefono si fosse "dimenticato" di fare alcune divisioni.

I miei strumenti SDK sono 22.3 (l'ultimo) e l'ho visto in build creati da IDEA di Eclipse e IntelliJ.

codice

attività:

package com.karmangames.mathtest; 

import android.app.Activity; 
import android.os.Bundle; 
import android.text.method.ScrollingMovementMethod; 
import android.widget.TextView; 

public class MathTestActivity extends Activity 
{ 
    /** 
    * Called when the activity is first created. 
    */ 
    @Override 
    public void onCreate(Bundle savedInstanceState) 
    { 
    super.onCreate(savedInstanceState); 
    setContentView(R.layout.main); 
    String s=""; 
    for(int n=0;n<=25;n++) 
     for(int k=0;k<=n;k++) 
     { 
     double v=C_n_k_double(n,k); 
     s+="C("+n+","+k+")="+v+(v==C_n_k_long(n,k) ? "" : " Correct is "+C_n_k_long(n,k))+"\n"; 
     if(k==n) 
      s+="\n"; 
     } 
    System.out.println(s); 
    ((TextView)findViewById(R.id.text)).setText(s); 
    ((TextView)findViewById(R.id.text)).setMovementMethod(new ScrollingMovementMethod()); 
    } 

    protected double C_n_k_double(int n, int k) 
    { 
    if(k<0 || k>n) 
     return 0; 
    //C_n^k 
    double s=1; 
    for(int i=1;i<=k;i++) 
     s=s*(n+1-i)/i; 
    return s; 
    } 

    protected double C_n_k_long(int n, int k) 
    { 
    if(k<0 || k>n) 
     return 0; 
    //C_n^k 
    long s=1; 
    for(int i=1;i<=k;i++) 
     s=s*(n+1-i)/i; 
    return (double)s; 
    } 

} 

main.xml:

<?xml version="1.0" encoding="utf-8"?> 
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android" 
       android:orientation="vertical" 
       android:layout_width="fill_parent" 
       android:layout_height="fill_parent" 
    > 

    <TextView 
    android:layout_width="fill_parent" 
    android:layout_height="wrap_content" 
    android:id="@+id/text" 
    android:text="Hello World!" 
    /> 
</LinearLayout> 

Esempio di risultati di calcolo sbagliato (ricordate, è diverso ogni volta ho provato)

C(0,0)=1.0 

C(1,0)=1.0 
C(1,1)=1.0 

C(2,0)=1.0 
C(2,1)=2.0 
C(2,2)=1.0 

C(3,0)=1.0 
C(3,1)=3.0 
C(3,2)=3.0 
C(3,3)=1.0 

C(4,0)=1.0 
C(4,1)=4.0 
C(4,2)=6.0 
C(4,3)=4.0 
C(4,4)=1.0 

C(5,0)=1.0 
C(5,1)=5.0 
C(5,2)=10.0 
C(5,3)=10.0 
C(5,4)=30.0 Correct is 5.0 
C(5,5)=1.0 

C(6,0)=1.0 
C(6,1)=6.0 
C(6,2)=15.0 
C(6,3)=40.0 Correct is 20.0 
C(6,4)=90.0 Correct is 15.0 
C(6,5)=144.0 Correct is 6.0 
C(6,6)=120.0 Correct is 1.0 

C(7,0)=1.0 
C(7,1)=7.0 
C(7,2)=21.0 
C(7,3)=35.0 
C(7,4)=105.0 Correct is 35.0 
C(7,5)=504.0 Correct is 21.0 
C(7,6)=840.0 Correct is 7.0 
C(7,7)=720.0 Correct is 1.0 

C(8,0)=1.0 
C(8,1)=8.0 
C(8,2)=28.0 
C(8,3)=112.0 Correct is 56.0 
C(8,4)=70.0 
C(8,5)=1344.0 Correct is 56.0 
C(8,6)=3360.0 Correct is 28.0 
C(8,7)=5760.0 Correct is 8.0 
C(8,8)=5040.0 Correct is 1.0 

C(9,0)=1.0 
C(9,1)=9.0 
C(9,2)=36.0 
C(9,3)=168.0 Correct is 84.0 
C(9,4)=756.0 Correct is 126.0 
C(9,5)=3024.0 Correct is 126.0 
C(9,6)=10080.0 Correct is 84.0 
C(9,7)=25920.0 Correct is 36.0 
C(9,8)=45360.0 Correct is 9.0 
C(9,9)=40320.0 Correct is 1.0 

C(10,0)=1.0 
C(10,1)=10.0 
C(10,2)=45.0 
C(10,3)=120.0 
C(10,4)=210.0 
C(10,5)=252.0 
C(10,6)=25200.0 Correct is 210.0 
C(10,7)=120.0 
C(10,8)=315.0 Correct is 45.0 
C(10,9)=16800.0 Correct is 10.0 
C(10,10)=1.0 
+2

Suoni molto improbabili. Hai provato a registrare ogni valore di 's' in quel ciclo per capire come differisce il calcolo? – zapl

+0

Qual è "corretto?" se entrambi? – DoubleDouble

+0

FWIW, in matematica, C (12, 4) = 495. – rgettman

risposta

3

Android membro del team ha pubblicato una possibile soluzione in un commento al mio issue. Se aggiungo android:vmSafeMode="true" a application elemento di manifest-file, tutti i calcoli vengono eseguiti correttamente. Questa opzione non è ben documentata e onestamente non so quanto influirà sulla velocità, ma almeno la matematica sarà corretta. La contrassegnerò come risposta corretta finché non ne verrà trovato uno migliore.

2

L'originale il codice e il codice elaborato funzionano bene sulla VM Java e sulla maggior parte delle macchine virtuali Dalvik, quindi devono essere validi. Se il codice elaborato produce risultati spuri su alcune macchine virtuali Dalvik, è probabile che il problema sia causato dal compilatore JIT in quelle VM. Il team Android di Google dovrebbe quindi esaminarlo.

L'ottimizzazione più ovvia che ProGuard applica qui consiste nell'integrare il metodo. Alcune istruzioni di ramo e variabili locali sono riordinate nel bytecode finale, ma il flusso di esecuzione di questo piccolo pezzo di codice è fondamentalmente lo stesso. È difficile determinare in che modo ProGuard potrebbe evitare il problema. Puoi disabilitare completamente la fase di ottimizzazione.

È possibile verificare se l'inserimento manuale del codice causa gli stessi problemi, senza ProGuard (il problema non sembra verificarsi sui miei dispositivi).

(Io sono l'autore di ProGuard)

+0

Grazie, Eric! Stavo per postare un problema al team di Android, volevo solo aspettare un giorno in caso mi fosse sfuggito qualcosa di ovvio e qualcuno lo indicasse. Uso ProGuard per lo sviluppo mobile da circa 10 anni e tu fai un ottimo lavoro. Continuate così! – Dmitry

+0

Eric, ho controllato alcune opzioni: '-dontoptimize' non aiuta,' -dontobfuscate' aiuta, ma chi vuole codice non offuscato in progetti commerciali? Non penso che un metodo sia stato delineato, perché vedo tutti e 3 i metodi in 'mapping.txt'. Sfortunatamente mi sono passato a MacOS qualche tempo fa e mi sono perso alcuni strumenti che ho utilizzato per il reverse engineering. Ho pubblicato un problema 63790 per Android, e spero di ottenere una risposta, ma non credo che lo sarà presto. – Dmitry

+1

Il passaggio di annullamento rinomina solo i metodi di 'a' e 'b' e rimuove le informazioni di debug sulle variabili locali, ma in effetti fa sì che il compilatore 'dx' emetta un bytecode differente. Puoi provare se '-keepattributes LocalVariableTable' fa la differenza. Puoi usare 'dexdump' da Android SDK per vedere il bytecode dell'applicazione. –

1

Questo risulta essere un bug del compilatore JIT che le ottimizzazioni di ProGuard si sono appena verificate.

Come AOSP issue spiega:

C'era una finestra nel tempo di rilascio del fagiolo di gelatina in cui la squadra avrebbe erroneamente ottimizzare distanza usi di galleggiamento doppie costanti in virgola che erano identici nelle basse 32 bit (e anche avuto un paio di altre condizioni soddisfatte). Il difetto è stato introdotto a fine novembre 2012 nell'albero interno di Google e nel febbraio 2013 in aosp. Risolto nell'aprile del 2013.

spiegazione più dettagliata in questo altro AOSP issue.