Add Yuval's fix for decomposition
MODIFY
WalletWasabi.Tests/UnitTests/WabiSabi/Client/GreedyDecomposerTests.cs
WalletWasabi.Tests/UnitTests/WabiSabi/Client/GreedyDecomposerTests.cs
@@ -32,9 +32,9 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
public void Decompose1Test(long amount, long[] expected)
{
var decomposer = new GreedyDecomposer(new Money[] { new(1L), new(2L), new(5L), new(10L) });
- var amounts = decomposer.Decompose(Money.Satoshis(amount), Money.Zero);
- Assert.Equal(Money.Satoshis(amount), amounts.Sum());
- Assert.Equal(expected, amounts.Select(x => x.Satoshi));
+ var decomposition = decomposer.Decompose(Money.Satoshis(amount), Money.Zero);
+ Assert.Equal(Money.Satoshis(amount), decomposition.Sum());
+ Assert.Equal(expected, decomposition.Select(x => x.Satoshi));
}
[Theory]
@@ -62,9 +62,9 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
public void Decompose2Test(long amount, long[] expected)
{
var decomposer = new GreedyDecomposer(new Money[] { new(1L), new(3L), new(11L) });
- var amounts = decomposer.Decompose(Money.Satoshis(amount), Money.Zero);
- Assert.Equal(Money.Satoshis(amount), amounts.Sum());
- Assert.Equal(expected, amounts.Select(x => x.Satoshi));
+ var decomposition = decomposer.Decompose(Money.Satoshis(amount), Money.Zero);
+ Assert.Equal(Money.Satoshis(amount), decomposition.Sum());
+ Assert.Equal(expected, decomposition.Select(x => x.Satoshi));
}
[Theory]
@@ -92,8 +92,43 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
public void DecomposeWithFee(long amount, long[] expected)
{
var decomposer = new GreedyDecomposer(new Money[] { new(1L), new(3L), new(11L) });
- var amounts = decomposer.Decompose(Money.Satoshis(amount), new Money(1L));
- Assert.Equal(expected, amounts.Select(x => x.Satoshi));
+ var costPerOutput = Money.Satoshis(1);
+ var decomposition = decomposer.Decompose(Money.Satoshis(amount), costPerOutput);
+ var totalCost = decomposition.Sum() + costPerOutput * decomposition.Count();
+ Assert.InRange(Money.Satoshis(amount) - totalCost, Money.Zero, decomposer.Denominations.Last());
+ Assert.Equal(expected, decomposition.Select(x => x.Satoshi));
+ }
+
+ [Theory]
+ [InlineData(0, new long[] { })]
+ [InlineData(1, new long[] { })]
+ [InlineData(2, new long[] { })]
+ [InlineData(3, new long[] { })]
+ [InlineData(4, new long[] { 3 })]
+ [InlineData(5, new long[] { 3 })]
+ [InlineData(6, new long[] { 3 })]
+ [InlineData(7, new long[] { 3 })]
+ [InlineData(8, new long[] { 3, 3 })]
+ [InlineData(9, new long[] { 3, 3 })]
+ [InlineData(10, new long[] { 3, 3 })]
+ [InlineData(11, new long[] { 3, 3 })]
+ [InlineData(12, new long[] { 11 })]
+ [InlineData(13, new long[] { 11 })]
+ [InlineData(14, new long[] { 11 })]
+ [InlineData(15, new long[] { 11 })]
+ [InlineData(16, new long[] { 11, 3 })]
+ [InlineData(17, new long[] { 11, 3 })]
+ [InlineData(18, new long[] { 11, 3 })]
+ [InlineData(19, new long[] { 11, 3 })]
+ [InlineData(38, new long[] { 11, 11, 11 })]
+ public void DecomposeWithFeeAndImplicitDustThreshold(long amount, long[] expected)
+ {
+ var decomposer = new GreedyDecomposer(new Money[] { new(3L), new(11L) });
+ var costPerOutput = Money.Satoshis(1);
+ var decomposition = decomposer.Decompose(Money.Satoshis(amount), costPerOutput);
+ var totalCost = decomposition.Sum() + costPerOutput * decomposition.Count();
+ Assert.InRange(Money.Satoshis(amount) - totalCost, Money.Zero, decomposer.Denominations.Last());
+ Assert.Equal(expected, decomposition.Select(x => x.Satoshi));
}
}
}

MODIFY
WalletWasabi/WabiSabi/Client/GreedyDecomposer.cs
WalletWasabi/WabiSabi/Client/GreedyDecomposer.cs
@@ -11,32 +11,22 @@ namespace WalletWasabi.WabiSabi.Client
public GreedyDecomposer(IEnumerable<Money> denominations)
{
Denominations = denominations.Any()
- ? denominations.OrderByDescending(x => x).ToImmutableList()
+ ? denominations.OrderByDescending(x => x).ToImmutableArray()
: throw new ArgumentException($"Argument {nameof(denominations)} has no elements");
}
- public ImmutableList<Money> Denominations { get; }
+ public ImmutableArray<Money> Denominations { get; }
public IEnumerable<Money> Decompose(Money amount, Money costPerOutput)
{
- var i = 0;
- var denomination = Denominations[i];
- while (amount - costPerOutput > Money.Zero)
+ for (var i = 0; i < Denominations.Length && costPerOutput < amount; i++)
{
- if (denomination <= amount - costPerOutput)
+ var denomination = Denominations[i];
+
+ while (denomination + costPerOutput <= amount)
{
- yield return denomination;
amount -= denomination + costPerOutput;
- }
- else if ((i + 1) < Denominations.Count)
- {
- i++;
- denomination = Denominations[i];
- }
- else
- {
- yield return amount;
- break;
+ yield return denomination;
}
}
}

Add Yuval's fix for decomposition