Add SSAT, SSAT16, USAT and USAT16 ARM32 instructions (#954)

* Implement SMULWB, SMULWT, SMLAWB, SMLAWT, and add tests for some multiply instructions

* Improve test descriptions

* Rename SMULH to SMUL__

* Add SSAT, SSAT16, USAT and USAT16 ARM32 instructions

* Fix new tests

* Replace AND 0xFFFF with 16-bits zero extension (more efficient)

4 files changed, 265 insertions, 40 deletions

diff --git a/ARMeilleure/Instructions/InstEmitAlu32.cs b/ARMeilleure/Instructions/InstEmitAlu32.cs
index 4d03f5c2..469a18a0 100644
--- a/ARMeilleure/Instructions/InstEmitAlu32.cs
+++ b/ARMeilleure/Instructions/InstEmitAlu32.cs
@@ -389,6 +389,20 @@ namespace ARMeilleure.Instructions
             EmitDiv(context, false);
         }
 
+        public static void Ssat(ArmEmitterContext context)
+        {
+            OpCode32Sat op = (OpCode32Sat)context.CurrOp;
+
+            EmitSat(context, -(1 << op.SatImm), (1 << op.SatImm) - 1);
+        }
+
+        public static void Ssat16(ArmEmitterContext context)
+        {
+            OpCode32Sat16 op = (OpCode32Sat16)context.CurrOp;
+
+            EmitSat16(context, -(1 << op.SatImm), (1 << op.SatImm) - 1);
+        }
+
         public static void Sub(ArmEmitterContext context)
         {
             IOpCode32Alu op = (IOpCode32Alu)context.CurrOp;
@@ -460,6 +474,20 @@ namespace ARMeilleure.Instructions
             EmitDiv(context, true);
         }
 
+        public static void Usat(ArmEmitterContext context)
+        {
+            OpCode32Sat op = (OpCode32Sat)context.CurrOp;
+
+            EmitSat(context, 0, op.SatImm == 32 ? (int)(~0) : (1 << op.SatImm) - 1);
+        }
+
+        public static void Usat16(ArmEmitterContext context)
+        {
+            OpCode32Sat16 op = (OpCode32Sat16)context.CurrOp;
+
+            EmitSat16(context, 0, (1 << op.SatImm) - 1);
+        }
+
         public static void Uxtb(ArmEmitterContext context)
         {
             EmitSignExtend(context, false, 8);
@@ -553,7 +581,7 @@ namespace ARMeilleure.Instructions
                     lowAdd = context.ZeroExtend16(OperandType.I32, n);
                     highAdd = context.ZeroExtend16(OperandType.I32, context.ShiftRightUI(n, Const(16)));
                 }
-                
+
                 low16 = context.Add(low16, lowAdd);
                 high16 = context.Add(high16, highAdd);
             }
@@ -615,9 +643,116 @@ namespace ARMeilleure.Instructions
             context.MarkLabel(lblEnd);
         }
 
+        private static void EmitSat(ArmEmitterContext context, int intMin, int intMax)
+        {
+            OpCode32Sat op = (OpCode32Sat)context.CurrOp;
+
+            Operand n = GetIntA32(context, op.Rn);
+
+            int shift = DecodeImmShift(op.ShiftType, op.Imm5);
+
+            switch (op.ShiftType)
+            {
+                case ShiftType.Lsl:
+                    if (shift == 32)
+                    {
+                        n = Const(0);
+                    }
+                    else
+                    {
+                        n = context.ShiftLeft(n, Const(shift));
+                    }
+                    break;
+                case ShiftType.Asr:
+                    if (shift == 32)
+                    {
+                        n = context.ShiftRightSI(n, Const(31));
+                    }
+                    else
+                    {
+                        n = context.ShiftRightSI(n, Const(shift));
+                    }
+                    break;
+            }
+
+            Operand lblCheckLtIntMin = Label();
+            Operand lblNoSat = Label();
+            Operand lblEnd = Label();
+
+            context.BranchIfFalse(lblCheckLtIntMin, context.ICompareGreater(n, Const(intMax)));
+
+            SetFlag(context, PState.QFlag, Const(1));
+            SetIntA32(context, op.Rd, Const(intMax));
+            context.Branch(lblEnd);
+
+            context.MarkLabel(lblCheckLtIntMin);
+            context.BranchIfFalse(lblNoSat, context.ICompareLess(n, Const(intMin)));
+
+            SetFlag(context, PState.QFlag, Const(1));
+            SetIntA32(context, op.Rd, Const(intMin));
+            context.Branch(lblEnd);
+
+            context.MarkLabel(lblNoSat);
+
+            SetIntA32(context, op.Rd, n);
+
+            context.MarkLabel(lblEnd);
+        }
+
+        private static void EmitSat16(ArmEmitterContext context, int intMin, int intMax)
+        {
+            OpCode32Sat16 op = (OpCode32Sat16)context.CurrOp;
+
+            void SetD(int part, Operand value)
+            {
+                if (part == 0)
+                {
+                    SetIntA32(context, op.Rd, context.ZeroExtend16(OperandType.I32, value));
+                }
+                else
+                {
+                    SetIntA32(context, op.Rd, context.BitwiseOr(GetIntA32(context, op.Rd), context.ShiftLeft(value, Const(16))));
+                }
+            }
+
+            Operand n = GetIntA32(context, op.Rn);
+
+            Operand nLow = context.SignExtend16(OperandType.I32, n);
+            Operand nHigh = context.ShiftRightSI(n, Const(16));
+
+            for (int part = 0; part < 2; part++)
+            {
+                Operand nPart = part == 0 ? nLow : nHigh;
+
+                Operand lblCheckLtIntMin = Label();
+                Operand lblNoSat = Label();
+                Operand lblEnd = Label();
+
+                context.BranchIfFalse(lblCheckLtIntMin, context.ICompareGreater(nPart, Const(intMax)));
+
+                SetFlag(context, PState.QFlag, Const(1));
+                SetD(part, Const(intMax));
+                context.Branch(lblEnd);
+
+                context.MarkLabel(lblCheckLtIntMin);
+                context.BranchIfFalse(lblNoSat, context.ICompareLess(nPart, Const(intMin)));
+
+                SetFlag(context, PState.QFlag, Const(1));
+                SetD(part, Const(intMin));
+                context.Branch(lblEnd);
+
+                context.MarkLabel(lblNoSat);
+
+                SetD(part, nPart);
+
+                context.MarkLabel(lblEnd);
+            }
+        }
+
         private static void EmitAluStore(ArmEmitterContext context, Operand value)
         {
             IOpCode32Alu op = (IOpCode32Alu)context.CurrOp;
+
             EmitGenericAluStoreA32(context, op.Rd, op.SetFlags, value);
         }
     }
diff --git a/ARMeilleure/Instructions/InstEmitAluHelper.cs b/ARMeilleure/Instructions/InstEmitAluHelper.cs
index 3bb87f27..916a1da5 100644
--- a/ARMeilleure/Instructions/InstEmitAluHelper.cs
+++ b/ARMeilleure/Instructions/InstEmitAluHelper.cs
@@ -297,6 +297,21 @@ namespace ARMeilleure.Instructions
             return m;
         }
 
+        public static int DecodeImmShift(ShiftType shiftType, int shift)
+        {
+            if (shift == 0)
+            {
+                switch (shiftType)
+                {
+                    case ShiftType.Lsr: shift = 32; break;
+                    case ShiftType.Asr: shift = 32; break;
+                    case ShiftType.Ror: shift = 1;  break;
+                }
+            }
+
+            return shift;
+        }
+
         public static Operand GetMShiftedByReg(ArmEmitterContext context, OpCode32AluRsReg op, bool setCarry)
         {
             Operand m = GetIntA32(context, op.Rm);
@@ -328,7 +343,7 @@ namespace ARMeilleure.Instructions
             if (expected)
             {
                 context.BranchIfFalse(endLabel, boolValue);
-            } 
+            }
             else
             {
                 context.BranchIfTrue(endLabel, boolValue);
@@ -411,7 +426,7 @@ namespace ARMeilleure.Instructions
                     SetFlag(context, PState.CFlag, cOut);
                 }, false);
             }
-            
+
             return context.ConditionalSelect(shiftLarge, Const(0), result);
         }
 
diff --git a/ARMeilleure/Instructions/InstEmitMul32.cs b/ARMeilleure/Instructions/InstEmitMul32.cs
index e64f3568..6714c5fd 100644
--- a/ARMeilleure/Instructions/InstEmitMul32.cs
+++ b/ARMeilleure/Instructions/InstEmitMul32.cs
@@ -1,5 +1,6 @@
 using ARMeilleure.Decoders;
 using ARMeilleure.IntermediateRepresentation;
+using ARMeilleure.State;
 using ARMeilleure.Translation;
 using System;
 
@@ -53,27 +54,6 @@ namespace ARMeilleure.Instructions
             EmitAluStore(context, res);
         }
 
-        public static void Smull(ArmEmitterContext context)
-        {
-            OpCode32AluUmull op = (OpCode32AluUmull)context.CurrOp;
-
-            Operand n = context.SignExtend32(OperandType.I64, GetIntA32(context, op.Rn));
-            Operand m = context.SignExtend32(OperandType.I64, GetIntA32(context, op.Rm));
-
-            Operand res = context.Multiply(n, m);
-
-            Operand hi = context.ConvertI64ToI32(context.ShiftRightUI(res, Const(32)));
-            Operand lo = context.ConvertI64ToI32(res);
-
-            if (op.SetFlags)
-            {
-                EmitNZFlagsCheck(context, res);
-            }
-
-            EmitGenericAluStoreA32(context, op.RdHi, op.SetFlags, hi);
-            EmitGenericAluStoreA32(context, op.RdLo, op.SetFlags, lo);
-        }
-
         public static void Smmla(ArmEmitterContext context)
         {
             EmitSmmul(context, MullFlags.SignedAdd);
@@ -101,7 +81,7 @@ namespace ARMeilleure.Instructions
             if (flags.HasFlag(MullFlags.Add) && op.Ra != 0xf)
             {
                 res = context.Add(context.ShiftLeft(context.ZeroExtend32(OperandType.I64, GetIntA32(context, op.Ra)), Const(32)), res);
-            } 
+            }
             else if (flags.HasFlag(MullFlags.Subtract))
             {
                 res = context.Subtract(context.ShiftLeft(context.ZeroExtend32(OperandType.I64, GetIntA32(context, op.Ra)), Const(32)), res);
@@ -117,37 +97,40 @@ namespace ARMeilleure.Instructions
             EmitGenericAluStoreA32(context, op.Rd, false, hi);
         }
 
-        public static void Smlab(ArmEmitterContext context)
+        public static void Smla__(ArmEmitterContext context)
         {
             OpCode32AluMla op = (OpCode32AluMla)context.CurrOp;
 
             Operand n = GetIntA32(context, op.Rn);
             Operand m = GetIntA32(context, op.Rm);
+            Operand a = GetIntA32(context, op.Ra);
 
             if (op.NHigh)
             {
-                n = context.SignExtend16(OperandType.I32, context.ShiftRightUI(n, Const(16)));
+                n = context.SignExtend16(OperandType.I64, context.ShiftRightUI(n, Const(16)));
             }
             else
             {
-                n = context.SignExtend16(OperandType.I32, n);
+                n = context.SignExtend16(OperandType.I64, n);
             }
 
             if (op.MHigh)
             {
-                m = context.SignExtend16(OperandType.I32, context.ShiftRightUI(m, Const(16)));
+                m = context.SignExtend16(OperandType.I64, context.ShiftRightUI(m, Const(16)));
             }
             else
             {
-                m = context.SignExtend16(OperandType.I32, m);
+                m = context.SignExtend16(OperandType.I64, m);
             }
 
             Operand res = context.Multiply(n, m);
 
-            Operand a = GetIntA32(context, op.Ra);
-            res = context.Add(res, a);
+            Operand toAdd = context.SignExtend32(OperandType.I64, a);
+            res = context.Add(res, toAdd);
+            Operand q = context.ICompareNotEqual(res, context.SignExtend32(OperandType.I64, res));
+            res = context.ConvertI64ToI32(res);
 
-            // TODO: set Q flag when last addition overflows (saturation)?
+            UpdateQFlag(context, q);
 
             EmitGenericAluStoreA32(context, op.Rd, false, res);
         }
@@ -157,7 +140,7 @@ namespace ARMeilleure.Instructions
             EmitMlal(context, true);
         }
 
-        public static void Smlalh(ArmEmitterContext context)
+        public static void Smlal__(ArmEmitterContext context)
         {
             OpCode32AluUmull op = (OpCode32AluUmull)context.CurrOp;
 
@@ -167,7 +150,7 @@ namespace ARMeilleure.Instructions
             if (op.NHigh)
             {
                 n = context.SignExtend16(OperandType.I64, context.ShiftRightUI(n, Const(16)));
-            } 
+            }
             else
             {
                 n = context.SignExtend16(OperandType.I64, n);
@@ -176,7 +159,7 @@ namespace ARMeilleure.Instructions
             if (op.MHigh)
             {
                 m = context.SignExtend16(OperandType.I64, context.ShiftRightUI(m, Const(16)));
-            } 
+            }
             else
             {
                 m = context.SignExtend16(OperandType.I64, m);
@@ -195,7 +178,37 @@ namespace ARMeilleure.Instructions
             EmitGenericAluStoreA32(context, op.RdLo, false, lo);
         }
 
-        public static void Smulh(ArmEmitterContext context)
+        public static void Smlaw_(ArmEmitterContext context)
+        {
+            OpCode32AluMla op = (OpCode32AluMla)context.CurrOp;
+
+            Operand n = GetIntA32(context, op.Rn);
+            Operand m = GetIntA32(context, op.Rm);
+            Operand a = GetIntA32(context, op.Ra);
+
+            if (op.MHigh)
+            {
+                m = context.SignExtend16(OperandType.I64, context.ShiftRightUI(m, Const(16)));
+            }
+            else
+            {
+                m = context.SignExtend16(OperandType.I64, m);
+            }
+
+            Operand res = context.Multiply(context.SignExtend32(OperandType.I64, n), m);
+
+            Operand toAdd = context.ShiftLeft(context.SignExtend32(OperandType.I64, a), Const(16));
+            res = context.Add(res, toAdd);
+            res = context.ShiftRightSI(res, Const(16));
+            Operand q = context.ICompareNotEqual(res, context.SignExtend32(OperandType.I64, res));
+            res = context.ConvertI64ToI32(res);
+
+            UpdateQFlag(context, q);
+
+            EmitGenericAluStoreA32(context, op.Rd, false, res);
+        }
+
+        public static void Smul__(ArmEmitterContext context)
         {
             OpCode32AluMla op = (OpCode32AluMla)context.CurrOp;
 
@@ -225,6 +238,51 @@ namespace ARMeilleure.Instructions
             EmitGenericAluStoreA32(context, op.Rd, false, res);
         }
 
+        public static void Smull(ArmEmitterContext context)
+        {
+            OpCode32AluUmull op = (OpCode32AluUmull)context.CurrOp;
+
+            Operand n = context.SignExtend32(OperandType.I64, GetIntA32(context, op.Rn));
+            Operand m = context.SignExtend32(OperandType.I64, GetIntA32(context, op.Rm));
+
+            Operand res = context.Multiply(n, m);
+
+            Operand hi = context.ConvertI64ToI32(context.ShiftRightUI(res, Const(32)));
+            Operand lo = context.ConvertI64ToI32(res);
+
+            if (op.SetFlags)
+            {
+                EmitNZFlagsCheck(context, res);
+            }
+
+            EmitGenericAluStoreA32(context, op.RdHi, op.SetFlags, hi);
+            EmitGenericAluStoreA32(context, op.RdLo, op.SetFlags, lo);
+        }
+
+        public static void Smulw_(ArmEmitterContext context)
+        {
+            OpCode32AluMla op = (OpCode32AluMla)context.CurrOp;
+
+            Operand n = GetIntA32(context, op.Rn);
+            Operand m = GetIntA32(context, op.Rm);
+
+            if (op.MHigh)
+            {
+                m = context.SignExtend16(OperandType.I64, context.ShiftRightUI(m, Const(16)));
+            }
+            else
+            {
+                m = context.SignExtend16(OperandType.I64, m);
+            }
+
+            Operand res = context.Multiply(context.SignExtend32(OperandType.I64, n), m);
+
+            res = context.ShiftRightUI(res, Const(16));
+            res = context.ConvertI64ToI32(res);
+
+            EmitGenericAluStoreA32(context, op.Rd, false, res);
+        }
+
         public static void Umlal(ArmEmitterContext context)
         {
             EmitMlal(context, false);
@@ -286,5 +344,16 @@ namespace ARMeilleure.Instructions
             EmitGenericAluStoreA32(context, op.RdHi, op.SetFlags, hi);
             EmitGenericAluStoreA32(context, op.RdLo, op.SetFlags, lo);
         }
+
+        private static void UpdateQFlag(ArmEmitterContext context, Operand q)
+        {
+            Operand lblSkipSetQ = Label();
+
+            context.BranchIfFalse(lblSkipSetQ, q);
+
+            SetFlag(context, PState.QFlag, Const(1));
+
+            context.MarkLabel(lblSkipSetQ);
+        }
     }
 }
diff --git a/ARMeilleure/Instructions/InstName.cs b/ARMeilleure/Instructions/InstName.cs
index 157feacf..049c956d 100644
--- a/ARMeilleure/Instructions/InstName.cs
+++ b/ARMeilleure/Instructions/InstName.cs
@@ -81,8 +81,11 @@ namespace ARMeilleure.Instructions
         Sdiv,
         Smaddl,
         Smsubl,
-        Smulh,
+        Smul__,
         Smull,
+        Smulw_,
+        Ssat,
+        Ssat16,
         Stlr,
         Stlxp,
         Stlxr,
@@ -491,9 +494,10 @@ namespace ARMeilleure.Instructions
         Rsb,
         Rsc,
         Sbfx,
-        Smlab,
+        Smla__,
         Smlal,
-        Smlalh,
+        Smlal__,
+        Smlaw_,
         Smmla,
         Smmls,
         Smmul,
@@ -519,6 +523,8 @@ namespace ARMeilleure.Instructions
         Ubfx,
         Umlal,
         Umull,
+        Usat,
+        Usat16,
         Uxtb,
         Uxtb16,
         Uxth,