Skip to main content

voirs_spatial/
types.rs

1//! Core types for spatial audio processing
2
3use serde::{Deserialize, Serialize};
4use std::time::Duration;
5
6#[cfg(target_arch = "x86_64")]
7use std::arch::x86_64::*;
8
9#[cfg(target_arch = "aarch64")]
10use std::arch::aarch64::*;
11
12/// 3D position in space
13#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
14pub struct Position3D {
15    /// X coordinate (left-right)
16    pub x: f32,
17    /// Y coordinate (up-down)
18    pub y: f32,
19    /// Z coordinate (front-back)
20    pub z: f32,
21}
22
23impl Position3D {
24    /// Create new position
25    pub fn new(x: f32, y: f32, z: f32) -> Self {
26        Self { x, y, z }
27    }
28
29    /// Distance to another position
30    pub fn distance_to(&self, other: &Position3D) -> f32 {
31        let dx = self.x - other.x;
32        let dy = self.y - other.y;
33        let dz = self.z - other.z;
34        (dx * dx + dy * dy + dz * dz).sqrt()
35    }
36
37    /// Calculate dot product with another position vector
38    pub fn dot(&self, other: &Position3D) -> f32 {
39        self.x * other.x + self.y * other.y + self.z * other.z
40    }
41
42    /// Get normalized vector (unit vector)
43    pub fn normalized(&self) -> Position3D {
44        let length = (self.x * self.x + self.y * self.y + self.z * self.z).sqrt();
45        if length > 0.0 {
46            Position3D::new(self.x / length, self.y / length, self.z / length)
47        } else {
48            *self
49        }
50    }
51
52    /// Get magnitude/length of the vector
53    pub fn magnitude(&self) -> f32 {
54        (self.x * self.x + self.y * self.y + self.z * self.z).sqrt()
55    }
56
57    /// Cross product with another vector
58    pub fn cross(&self, other: &Position3D) -> Position3D {
59        Position3D::new(
60            self.y * other.z - self.z * other.y,
61            self.z * other.x - self.x * other.z,
62            self.x * other.y - self.y * other.x,
63        )
64    }
65
66    /// Vector addition
67    pub fn add(&self, other: &Position3D) -> Position3D {
68        Position3D::new(self.x + other.x, self.y + other.y, self.z + other.z)
69    }
70
71    /// Vector subtraction
72    pub fn sub(&self, other: &Position3D) -> Position3D {
73        Position3D::new(self.x - other.x, self.y - other.y, self.z - other.z)
74    }
75
76    /// Scalar multiplication
77    pub fn scale(&self, scalar: f32) -> Position3D {
78        Position3D::new(self.x * scalar, self.y * scalar, self.z * scalar)
79    }
80
81    /// Linear interpolation between two positions
82    pub fn lerp(&self, other: &Position3D, t: f32) -> Position3D {
83        Position3D::new(
84            self.x + (other.x - self.x) * t,
85            self.y + (other.y - self.y) * t,
86            self.z + (other.z - self.z) * t,
87        )
88    }
89}
90
91/// SIMD-optimized spatial calculations
92pub struct SIMDSpatialOps;
93
94impl SIMDSpatialOps {
95    /// Calculate distances from one position to multiple positions using SIMD
96    #[cfg(target_feature = "sse2")]
97    #[allow(unsafe_code)]
98    pub fn distances_simd(from: Position3D, positions: &[Position3D]) -> Vec<f32> {
99        let mut distances = Vec::with_capacity(positions.len());
100
101        unsafe {
102            let from_x = _mm_set1_ps(from.x);
103            let from_y = _mm_set1_ps(from.y);
104            let from_z = _mm_set1_ps(from.z);
105
106            let mut i = 0;
107            while i + 4 <= positions.len() {
108                // Load 4 positions at once
109                let x_vals = _mm_set_ps(
110                    positions[i + 3].x,
111                    positions[i + 2].x,
112                    positions[i + 1].x,
113                    positions[i].x,
114                );
115                let y_vals = _mm_set_ps(
116                    positions[i + 3].y,
117                    positions[i + 2].y,
118                    positions[i + 1].y,
119                    positions[i].y,
120                );
121                let z_vals = _mm_set_ps(
122                    positions[i + 3].z,
123                    positions[i + 2].z,
124                    positions[i + 1].z,
125                    positions[i].z,
126                );
127
128                // Calculate differences
129                let dx = _mm_sub_ps(x_vals, from_x);
130                let dy = _mm_sub_ps(y_vals, from_y);
131                let dz = _mm_sub_ps(z_vals, from_z);
132
133                // Square the differences
134                let dx2 = _mm_mul_ps(dx, dx);
135                let dy2 = _mm_mul_ps(dy, dy);
136                let dz2 = _mm_mul_ps(dz, dz);
137
138                // Sum and take square root
139                let sum = _mm_add_ps(_mm_add_ps(dx2, dy2), dz2);
140                let sqrt_vals = _mm_sqrt_ps(sum);
141
142                // Extract results
143                let mut result = [0.0f32; 4];
144                _mm_storeu_ps(result.as_mut_ptr(), sqrt_vals);
145
146                distances.extend_from_slice(&result);
147
148                i += 4;
149            }
150
151            // Handle remaining positions
152            for pos in &positions[i..] {
153                distances.push(from.distance_to(pos));
154            }
155        }
156
157        distances
158    }
159
160    /// Fallback non-SIMD version for compatibility
161    pub fn distances_fallback(from: Position3D, positions: &[Position3D]) -> Vec<f32> {
162        positions.iter().map(|pos| from.distance_to(pos)).collect()
163    }
164
165    /// Automatic distance calculation with SIMD when available
166    pub fn distances(from: Position3D, positions: &[Position3D]) -> Vec<f32> {
167        #[cfg(all(target_feature = "sse2", target_arch = "x86_64"))]
168        {
169            Self::distances_simd(from, positions)
170        }
171        #[cfg(not(all(target_feature = "sse2", target_arch = "x86_64")))]
172        {
173            Self::distances_fallback(from, positions)
174        }
175    }
176
177    /// SIMD-optimized vector normalization for multiple positions
178    #[cfg(target_feature = "sse2")]
179    #[allow(unsafe_code)]
180    pub fn normalize_batch_simd(positions: &mut [Position3D]) {
181        unsafe {
182            let mut i = 0;
183            while i + 4 <= positions.len() {
184                // Load 4 positions
185                let x_vals = _mm_set_ps(
186                    positions[i + 3].x,
187                    positions[i + 2].x,
188                    positions[i + 1].x,
189                    positions[i].x,
190                );
191                let y_vals = _mm_set_ps(
192                    positions[i + 3].y,
193                    positions[i + 2].y,
194                    positions[i + 1].y,
195                    positions[i].y,
196                );
197                let z_vals = _mm_set_ps(
198                    positions[i + 3].z,
199                    positions[i + 2].z,
200                    positions[i + 1].z,
201                    positions[i].z,
202                );
203
204                // Calculate magnitude squared
205                let x2 = _mm_mul_ps(x_vals, x_vals);
206                let y2 = _mm_mul_ps(y_vals, y_vals);
207                let z2 = _mm_mul_ps(z_vals, z_vals);
208                let mag2 = _mm_add_ps(_mm_add_ps(x2, y2), z2);
209
210                // Calculate reciprocal square root (1/sqrt(mag2))
211                let rsqrt = _mm_rsqrt_ps(mag2);
212
213                // Refine the approximation (Newton-Raphson iteration)
214                let half = _mm_set1_ps(0.5);
215                let three = _mm_set1_ps(3.0);
216                let rsqrt_refined = _mm_mul_ps(
217                    rsqrt,
218                    _mm_sub_ps(three, _mm_mul_ps(_mm_mul_ps(mag2, rsqrt), rsqrt)),
219                );
220                let inv_mag = _mm_mul_ps(half, rsqrt_refined);
221
222                // Normalize the vectors
223                let norm_x = _mm_mul_ps(x_vals, inv_mag);
224                let norm_y = _mm_mul_ps(y_vals, inv_mag);
225                let norm_z = _mm_mul_ps(z_vals, inv_mag);
226
227                // Store results back
228                let mut x_result = [0.0f32; 4];
229                let mut y_result = [0.0f32; 4];
230                let mut z_result = [0.0f32; 4];
231
232                _mm_storeu_ps(x_result.as_mut_ptr(), norm_x);
233                _mm_storeu_ps(y_result.as_mut_ptr(), norm_y);
234                _mm_storeu_ps(z_result.as_mut_ptr(), norm_z);
235
236                for j in 0..4 {
237                    positions[i + j].x = x_result[j];
238                    positions[i + j].y = y_result[j];
239                    positions[i + j].z = z_result[j];
240                }
241
242                i += 4;
243            }
244
245            // Handle remaining positions
246            for pos in &mut positions[i..] {
247                *pos = pos.normalized();
248            }
249        }
250    }
251
252    /// Fallback batch normalization
253    pub fn normalize_batch_fallback(positions: &mut [Position3D]) {
254        for pos in positions {
255            *pos = pos.normalized();
256        }
257    }
258
259    /// Automatic batch normalization
260    pub fn normalize_batch(positions: &mut [Position3D]) {
261        #[cfg(all(target_feature = "sse2", target_arch = "x86_64"))]
262        {
263            Self::normalize_batch_simd(positions);
264        }
265        #[cfg(not(all(target_feature = "sse2", target_arch = "x86_64")))]
266        {
267            Self::normalize_batch_fallback(positions);
268        }
269    }
270
271    /// SIMD-optimized dot product calculations
272    #[cfg(target_feature = "sse2")]
273    #[allow(unsafe_code)]
274    pub fn dot_products_simd(a_positions: &[Position3D], b_positions: &[Position3D]) -> Vec<f32> {
275        assert_eq!(a_positions.len(), b_positions.len());
276        let mut results = Vec::with_capacity(a_positions.len());
277
278        unsafe {
279            let mut i = 0;
280            while i + 4 <= a_positions.len() {
281                // Load positions A
282                let ax = _mm_set_ps(
283                    a_positions[i + 3].x,
284                    a_positions[i + 2].x,
285                    a_positions[i + 1].x,
286                    a_positions[i].x,
287                );
288                let ay = _mm_set_ps(
289                    a_positions[i + 3].y,
290                    a_positions[i + 2].y,
291                    a_positions[i + 1].y,
292                    a_positions[i].y,
293                );
294                let az = _mm_set_ps(
295                    a_positions[i + 3].z,
296                    a_positions[i + 2].z,
297                    a_positions[i + 1].z,
298                    a_positions[i].z,
299                );
300
301                // Load positions B
302                let bx = _mm_set_ps(
303                    b_positions[i + 3].x,
304                    b_positions[i + 2].x,
305                    b_positions[i + 1].x,
306                    b_positions[i].x,
307                );
308                let by = _mm_set_ps(
309                    b_positions[i + 3].y,
310                    b_positions[i + 2].y,
311                    b_positions[i + 1].y,
312                    b_positions[i].y,
313                );
314                let bz = _mm_set_ps(
315                    b_positions[i + 3].z,
316                    b_positions[i + 2].z,
317                    b_positions[i + 1].z,
318                    b_positions[i].z,
319                );
320
321                // Calculate dot products
322                let xx = _mm_mul_ps(ax, bx);
323                let yy = _mm_mul_ps(ay, by);
324                let zz = _mm_mul_ps(az, bz);
325                let dots = _mm_add_ps(_mm_add_ps(xx, yy), zz);
326
327                // Extract results
328                let mut result = [0.0f32; 4];
329                _mm_storeu_ps(result.as_mut_ptr(), dots);
330
331                results.extend_from_slice(&result);
332
333                i += 4;
334            }
335
336            // Handle remaining pairs
337            for j in i..a_positions.len() {
338                results.push(a_positions[j].dot(&b_positions[j]));
339            }
340        }
341
342        results
343    }
344
345    /// Fallback dot product calculation
346    pub fn dot_products_fallback(
347        a_positions: &[Position3D],
348        b_positions: &[Position3D],
349    ) -> Vec<f32> {
350        assert_eq!(a_positions.len(), b_positions.len());
351        a_positions
352            .iter()
353            .zip(b_positions.iter())
354            .map(|(a, b)| a.dot(b))
355            .collect()
356    }
357
358    /// Automatic dot product calculation
359    pub fn dot_products(a_positions: &[Position3D], b_positions: &[Position3D]) -> Vec<f32> {
360        #[cfg(all(target_feature = "sse2", target_arch = "x86_64"))]
361        {
362            Self::dot_products_simd(a_positions, b_positions)
363        }
364        #[cfg(not(all(target_feature = "sse2", target_arch = "x86_64")))]
365        {
366            Self::dot_products_fallback(a_positions, b_positions)
367        }
368    }
369}
370
371impl Default for Position3D {
372    fn default() -> Self {
373        Self::new(0.0, 0.0, 0.0)
374    }
375}
376
377/// Audio channel configuration
378#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
379pub enum AudioChannel {
380    /// Mono audio
381    Mono,
382    /// Stereo audio (left/right)
383    Stereo,
384    /// Binaural audio for headphones
385    Binaural,
386    /// 5.1 surround sound
387    Surround5_1,
388    /// 7.1 surround sound
389    Surround7_1,
390}
391
392/// Binaural audio with left and right channels
393#[derive(Debug, Clone, Serialize, Deserialize)]
394pub struct BinauraAudio {
395    /// Left channel samples
396    pub left: Vec<f32>,
397    /// Right channel samples
398    pub right: Vec<f32>,
399    /// Sample rate
400    pub sample_rate: u32,
401}
402
403impl BinauraAudio {
404    /// Create new binaural audio
405    pub fn new(left: Vec<f32>, right: Vec<f32>, sample_rate: u32) -> Self {
406        Self {
407            left,
408            right,
409            sample_rate,
410        }
411    }
412
413    /// Get duration in seconds
414    pub fn duration(&self) -> f32 {
415        self.left.len() as f32 / self.sample_rate as f32
416    }
417}
418
419/// Spatial effect types
420#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
421pub enum SpatialEffect {
422    /// HRTF-based binaural rendering
423    Hrtf,
424    /// Room reverberation
425    Reverb,
426    /// Distance attenuation
427    DistanceAttenuation,
428    /// Doppler effect
429    Doppler,
430    /// Air absorption
431    AirAbsorption,
432}
433
434/// Request for spatial audio processing
435#[derive(Debug, Clone, Serialize, Deserialize)]
436pub struct SpatialRequest {
437    /// Request ID
438    pub id: String,
439    /// Input audio (mono)
440    pub audio: Vec<f32>,
441    /// Input sample rate
442    pub sample_rate: u32,
443    /// Sound source position
444    pub source_position: Position3D,
445    /// Listener position
446    pub listener_position: Position3D,
447    /// Listener orientation (yaw, pitch, roll in radians)
448    pub listener_orientation: (f32, f32, f32),
449    /// Effects to apply
450    pub effects: Vec<SpatialEffect>,
451    /// Processing parameters
452    pub parameters: std::collections::HashMap<String, f32>,
453}
454
455impl SpatialRequest {
456    /// Create new spatial request
457    pub fn new(
458        id: String,
459        audio: Vec<f32>,
460        sample_rate: u32,
461        source_position: Position3D,
462        listener_position: Position3D,
463    ) -> Self {
464        Self {
465            id,
466            audio,
467            sample_rate,
468            source_position,
469            listener_position,
470            listener_orientation: (0.0, 0.0, 0.0),
471            effects: vec![SpatialEffect::Hrtf],
472            parameters: std::collections::HashMap::new(),
473        }
474    }
475
476    /// Validate the request
477    pub fn validate(&self) -> crate::Result<()> {
478        if self.audio.is_empty() {
479            return Err(crate::Error::LegacyValidation(
480                "Audio cannot be empty".to_string(),
481            ));
482        }
483        if self.sample_rate == 0 {
484            return Err(crate::Error::LegacyValidation(
485                "Sample rate must be positive".to_string(),
486            ));
487        }
488        Ok(())
489    }
490}
491
492/// Result of spatial audio processing
493#[derive(Debug, Clone, Serialize, Deserialize)]
494pub struct SpatialResult {
495    /// Request ID
496    pub request_id: String,
497    /// Processed binaural audio
498    pub audio: BinauraAudio,
499    /// Processing time
500    pub processing_time: Duration,
501    /// Applied effects
502    pub applied_effects: Vec<SpatialEffect>,
503    /// Success flag
504    pub success: bool,
505    /// Error message if failed
506    pub error_message: Option<String>,
507}
508
509impl SpatialResult {
510    /// Create successful result
511    pub fn success(
512        request_id: String,
513        audio: BinauraAudio,
514        processing_time: Duration,
515        applied_effects: Vec<SpatialEffect>,
516    ) -> Self {
517        Self {
518            request_id,
519            audio,
520            processing_time,
521            applied_effects,
522            success: true,
523            error_message: None,
524        }
525    }
526
527    /// Create failed result
528    pub fn failure(request_id: String, error_message: String, processing_time: Duration) -> Self {
529        Self {
530            request_id,
531            audio: BinauraAudio::new(Vec::new(), Vec::new(), 0),
532            processing_time,
533            applied_effects: Vec::new(),
534            success: false,
535            error_message: Some(error_message),
536        }
537    }
538}
539
540#[cfg(test)]
541mod tests {
542    use super::*;
543
544    #[test]
545    fn test_position_distance() {
546        let pos1 = Position3D::new(0.0, 0.0, 0.0);
547        let pos2 = Position3D::new(3.0, 4.0, 0.0);
548        assert_eq!(pos1.distance_to(&pos2), 5.0);
549    }
550
551    #[test]
552    fn test_binaural_audio_duration() {
553        let audio = BinauraAudio::new(vec![0.0; 44100], vec![0.0; 44100], 44100);
554        assert_eq!(audio.duration(), 1.0);
555    }
556
557    #[test]
558    fn test_spatial_request_validation() {
559        let request = SpatialRequest::new(
560            "test".to_string(),
561            vec![0.1, 0.2, 0.3],
562            44100,
563            Position3D::default(),
564            Position3D::default(),
565        );
566        assert!(request.validate().is_ok());
567
568        let empty_request = SpatialRequest::new(
569            "test".to_string(),
570            Vec::new(),
571            44100,
572            Position3D::default(),
573            Position3D::default(),
574        );
575        assert!(empty_request.validate().is_err());
576    }
577
578    #[test]
579    fn test_position3d_additional_methods() {
580        let pos1 = Position3D::new(1.0, 2.0, 3.0);
581        let pos2 = Position3D::new(4.0, 5.0, 6.0);
582
583        // Test vector addition
584        let sum = pos1.add(&pos2);
585        assert_eq!(sum, Position3D::new(5.0, 7.0, 9.0));
586
587        // Test vector subtraction
588        let diff = pos2.sub(&pos1);
589        assert_eq!(diff, Position3D::new(3.0, 3.0, 3.0));
590
591        // Test scalar multiplication
592        let scaled = pos1.scale(2.0);
593        assert_eq!(scaled, Position3D::new(2.0, 4.0, 6.0));
594
595        // Test dot product
596        let dot = pos1.dot(&pos2);
597        assert_eq!(dot, 32.0); // 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32
598
599        // Test magnitude
600        let pos = Position3D::new(3.0, 4.0, 0.0);
601        assert_eq!(pos.magnitude(), 5.0);
602
603        // Test normalization
604        let normalized = pos.normalized();
605        assert!((normalized.magnitude() - 1.0).abs() < 0.001);
606
607        // Test linear interpolation
608        let pos_a = Position3D::new(0.0, 0.0, 0.0);
609        let pos_b = Position3D::new(10.0, 10.0, 10.0);
610        let mid = pos_a.lerp(&pos_b, 0.5);
611        assert_eq!(mid, Position3D::new(5.0, 5.0, 5.0));
612    }
613
614    #[test]
615    fn test_simd_distance_fallback() {
616        let from = Position3D::new(0.0, 0.0, 0.0);
617        let positions = vec![
618            Position3D::new(1.0, 0.0, 0.0),
619            Position3D::new(0.0, 1.0, 0.0),
620            Position3D::new(0.0, 0.0, 1.0),
621            Position3D::new(3.0, 4.0, 0.0),
622        ];
623
624        let distances = SIMDSpatialOps::distances_fallback(from, &positions);
625
626        assert_eq!(distances.len(), 4);
627        assert!((distances[0] - 1.0).abs() < 0.001);
628        assert!((distances[1] - 1.0).abs() < 0.001);
629        assert!((distances[2] - 1.0).abs() < 0.001);
630        assert!((distances[3] - 5.0).abs() < 0.001);
631    }
632
633    #[test]
634    fn test_simd_distance_automatic() {
635        let from = Position3D::new(0.0, 0.0, 0.0);
636        let positions = vec![
637            Position3D::new(1.0, 0.0, 0.0),
638            Position3D::new(0.0, 1.0, 0.0),
639            Position3D::new(0.0, 0.0, 1.0),
640            Position3D::new(3.0, 4.0, 0.0),
641        ];
642
643        let distances = SIMDSpatialOps::distances(from, &positions);
644
645        assert_eq!(distances.len(), 4);
646        assert!((distances[0] - 1.0).abs() < 0.001);
647        assert!((distances[1] - 1.0).abs() < 0.001);
648        assert!((distances[2] - 1.0).abs() < 0.001);
649        assert!((distances[3] - 5.0).abs() < 0.001);
650    }
651
652    #[test]
653    fn test_simd_normalize_batch_fallback() {
654        let mut positions = vec![
655            Position3D::new(3.0, 4.0, 0.0),
656            Position3D::new(5.0, 12.0, 0.0),
657            Position3D::new(8.0, 15.0, 0.0),
658        ];
659
660        SIMDSpatialOps::normalize_batch_fallback(&mut positions);
661
662        for pos in &positions {
663            assert!((pos.magnitude() - 1.0).abs() < 0.001);
664        }
665    }
666
667    #[test]
668    fn test_simd_normalize_batch_automatic() {
669        let mut positions = vec![
670            Position3D::new(3.0, 4.0, 0.0),
671            Position3D::new(5.0, 12.0, 0.0),
672            Position3D::new(8.0, 15.0, 0.0),
673            Position3D::new(1.0, 2.0, 3.0),
674            Position3D::new(4.0, 5.0, 6.0),
675        ];
676
677        SIMDSpatialOps::normalize_batch(&mut positions);
678
679        for pos in &positions {
680            assert!((pos.magnitude() - 1.0).abs() < 0.001);
681        }
682    }
683
684    #[test]
685    fn test_simd_dot_products_fallback() {
686        let a_positions = vec![
687            Position3D::new(1.0, 2.0, 3.0),
688            Position3D::new(4.0, 5.0, 6.0),
689            Position3D::new(7.0, 8.0, 9.0),
690        ];
691        let b_positions = vec![
692            Position3D::new(1.0, 1.0, 1.0),
693            Position3D::new(2.0, 2.0, 2.0),
694            Position3D::new(3.0, 3.0, 3.0),
695        ];
696
697        let dots = SIMDSpatialOps::dot_products_fallback(&a_positions, &b_positions);
698
699        assert_eq!(dots.len(), 3);
700        assert_eq!(dots[0], 6.0); // 1*1 + 2*1 + 3*1 = 6
701        assert_eq!(dots[1], 30.0); // 4*2 + 5*2 + 6*2 = 30
702        assert_eq!(dots[2], 72.0); // 7*3 + 8*3 + 9*3 = 72
703    }
704
705    #[test]
706    fn test_simd_dot_products_automatic() {
707        let a_positions = vec![
708            Position3D::new(1.0, 2.0, 3.0),
709            Position3D::new(4.0, 5.0, 6.0),
710            Position3D::new(7.0, 8.0, 9.0),
711            Position3D::new(10.0, 11.0, 12.0),
712        ];
713        let b_positions = vec![
714            Position3D::new(1.0, 1.0, 1.0),
715            Position3D::new(2.0, 2.0, 2.0),
716            Position3D::new(3.0, 3.0, 3.0),
717            Position3D::new(4.0, 4.0, 4.0),
718        ];
719
720        let dots = SIMDSpatialOps::dot_products(&a_positions, &b_positions);
721
722        assert_eq!(dots.len(), 4);
723        assert_eq!(dots[0], 6.0); // 1*1 + 2*1 + 3*1 = 6
724        assert_eq!(dots[1], 30.0); // 4*2 + 5*2 + 6*2 = 30
725        assert_eq!(dots[2], 72.0); // 7*3 + 8*3 + 9*3 = 72
726        assert_eq!(dots[3], 132.0); // 10*4 + 11*4 + 12*4 = 132
727    }
728}